## Starting from greed (local optimization)

The basic idea of greedy algorithm is as follows:

```
1. Decompose the problem to be solved into several subproblems, and solve the subproblems respectively to obtain the local optimal solution of the subproblem
2. Merge the local optimal solutions of the subproblems to obtain the results based on the local optimal solutions
```

The so-called greed is to focus on the current (local) optimal results without considering the whole (global). The two ideas correspond respectively**Local optimal solution**and**Global optimal solution**

As you can see,**The result of greedy local optimal integration is often not the global optimal solution**！ For example: 322. Change

```
Question:
Give you an integer array of coins to represent coins of different denominations; And an integer amount representing the total amount.
Calculate and return the minimum number of coins required to make up the total amount. If no coin combination can form a total amount, return - 1 。
You can think that the number of each coin is unlimited.
```

According to the greedy idea, from big to small**enumeration**For all coin denominations, priority should be given to using as many coins with large denominations as possible, so that the number of coins used will be as small as possible! The code is as follows

```
//Method 1: greedy algorithm
//Idea: greedy to get the local optimum, but it may not be the overall optimum, so there are use cases
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
let rest = amount;
let count = 0;
coins.sort((a, b) => b - a);
//Traversal from large to small
for (let coin of coins) {
//How many can be used to calculate the current face value
let currCount = Math.floor(rest / coin);
//Accumulate current denomination usage
count += currCount;
//Update the remaining face value after using the current face value
rest -= coin * currCount;
if (rest === 0) {
return count;
}
}
return -1;
};
```

Greed is not suitable for all problems (some use cases fail), because sometimes it is too greedy! For example:

```
Find the minimum number of coins when coins [0] = 5, coins [1] = 3 and K = 11
According to the "greedy idea", first select the coin with the largest face value, that is, 5, and put it into the wallet. Then, there are 6 elements to be solved (i.e. 11-5 = 6). At this time, again "greedy", put in a coin with a face value of 5 yuan. At this time, there is only 1 yuan left. If you put in 5, you can't just make up 11 yuan. But in fact, this problem has a solution (5 + 3 + 3 = 11).
```

This is it.**Excessive greed**Problems caused by**to flash back**The solution is just like: the elevator is overloaded. Down comes a fat man and up comes a thin man

```
//Method 2: backtracking + recursion
//Idea: use case failed
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
//Number of combined coins
let res = Infinity;
coins.sort((a, b) => b - a);
if (coins.length === 0) {
return -1;
}
/**
*Find the minimum number of coins from the current combination
* @param {*} coins
* @param {*} total
* @param {*} index
* @returns
*/
const getMinCoinCountOfValue = (coins, total, index) => {
if (index === coins.length) {
return Infinity;
}
let minResult = Infinity;
let currValue = coins[index];
let maxCount = Math.floor(total / currValue);
for (let count = maxCount; count >= 0; count--) {
let rest = total - count * currValue;
if (rest === 0) {
minResult = Math.min(minResult, count);
}
let restCount = getMinCoinCountOfValue(coins, rest, index + 1);
if (restCount === Infinity) {
if (count === 0) {
break;
}
continue;
}
minResult = Math.min(minResult, count + restCount);
}
return minResult;
};
/**
*Find all combinations that meet the conditions
* @param {*} coins
* @param {*} amount
* @param {*} index
*/
const getMinCoinCount = (coins, amount, index) => {
//Conditions for recursive termination
if (index === coins.length) {
//Getmincoincountofvalue() finds the minimum number of coins for the reordered coins
res = Math.min(res, getMinCoinCountOfValue(coins, amount, 0));
}
for (let i = index; i < coins.length; i++) {
// swap
[coins[index], coins[i]] = [coins[i], coins[index]];
//Make a choice
res = Math.min(res, getMinCoinCount(coins, amount, index + 1))[
//Backtracking undo selection
(coins[index], coins[i])
] = [coins[i], coins[index]];
}
};
getMinCoinCount(coins, amount, 0);
//If no coin combination can form a total amount, - 1 is returned
return res === Infinity ? -1 : res;
};
```

In fact, the arithmetic of backtracking recursion in method 2 and enumeration in method 1 are essentially the same**Enumeration problem**：**All the problems are listed and the optimal solution is selected**

The recursive process can actually be equivalent to a tree**Recursive tree**, if the time complexity of traversing a complete tree (enumerating all cases) is very high (exponential), and there are a large number of overlapping subproblems during traversal (refer to the recursive tree that draws the famous recursive solution of Fibonacci sequence). Therefore, sometimes it needs to be carried out through conditions**Pruning optimization**。

**greedy**It is the recursive pruning optimization idea in 322. Change exchange method 2. corresponding**Recursive tree**The shortest path, but the shortest path is often not the obtained solution, so it is necessary to backtrack and traverse other paths. In comparison, enumerating all cases can save a lot of complexity.

## Overlapping subproblem (memory search)

in order to**Eliminate common duplicate subproblems**, it is necessary to adopt other ideas to optimize the commonly used means**State storage**or**Memory search** **memorization**

For example: 322. Change

```
//Method 3: recursive + memory search
//Idea: there are a lot of repetitions in enumeration. Use memo to cache the repeatedly calculated values
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
//Number of combined coins
let res = Infinity;
//Cache the repeatedly calculated value. Memo [total] indicates that the currency value is the minimum number of coins that total can exchange. If there is no cache, it is - 2
const memo = new Array(amount + 1).fill(-2);
//The result corresponding to 0 is 0
memo[0] = 0;
coins.sort((a, b) => b - a);
if (coins.length === 0) {
return -1;
}
/**
*Find the minimum number of coins that can be exchanged for total change
* @param {*} coins
* @param {*} total
* @returns
*/
const getMinCoinCount = (coins, total) => {
//Conditions for recursive termination
if (total < 0) {
return -1;
}
//Conditions for recursive termination
if (total === 0) {
return 0;
}
//First look for memo [total] from the cache
if (memo[total] !== -2) {
return memo[total];
}
let minCount = Infinity;
//Traverse all face values
for (let i = 0; i < coins.length; i++) {
//Skip if the current face value is greater than the total
if (coins[i] > total) {
continue;
}
//Use the current denomination and find the minimum number of coins for the remaining total
let restCount = getMinCoinCount(coins, total - coins[i]);
if (restCount === -1) {
//The currently selected coins [i] combination does not hold. Skip
continue;
}
//Update minimum total
let totalCount = 1 + restCount;
if (totalCount < minCount) {
minCount = totalCount;
}
}
//If no combination is available, - 1 is returned
if (minCount === Infinity) {
memo[total] = -1;
return -1;
}
//Update cache
memo[total] = minCount;
return minCount;
};
return getMinCoinCount(coins, amount);
};
```

Memory search is**top-down**Recursive process, the big problem is continuously disassembled into small problems, and then the small problems are solved one by one. Recursion is intuitive, but it does exist**Performance issues**(stack based, resulting in additional time and space overhead) and**Difficult to debug**And so on.

## Iterative and dynamic programming

In order to avoid the disadvantages of recursion (memory search), the top-down recursive implementation can be transformed into**Bottom up**of**iteration**realization.

If you have to deal with those small problems before dealing with each big problem, you can solve all the small problems first and then the big problems, which is**Bottom up**The process of.

If the subproblem is**Dependencies are one-way**, (a depends on B, but B does not depend directly or indirectly on a), then it can be solved directly from the bottom up.

```
//Method 5: dynamic programming
//Idea: bottom up, memory search
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
//Memo [total] indicates that the currency value is the minimum number of coins that total can exchange. If there is no cache, it is - 1
const memo = new Array(amount + 1).fill(-1);
//Initialization status
memo[0] = 0;
//Total currency status from 1 to amount
for (let v = 1; v <= amount; v++) {
//The minimum number of coins that can be rounded up corresponding to the total value of the current currency v
let minCount = Infinity;
//Enumerate the denominations of all coins for the total V value of the current currency
for (let i = 0; i < coins.length; i++) {
let currValue = coins[i];
//If the current face value is greater than the total currency value, skip
if (currValue > v) {
continue;
}
//Use the current face value to get the total remaining currency value
let rest = v - currValue;
//Extract the minimum number of coins corresponding to the total amount of remaining currency value from the cache
let restCount = memo[rest];
//- 1 indicates that the combination is not tenable
if (restCount == -1) {
continue;
}
//The current currency combination is established
let currCount = 1 + restCount;
//Update the minimum number of coins in the current currency value v
if (currCount < minCount) {
minCount = currCount;
}
}
//The minimum number of coins for the current total currency value V, if any, will be cached
if (minCount !== Infinity) {
memo[v] = minCount;
}
}
return memo[amount];
};
```

Yes, the solution process of this iterative memory search is**dynamic programming**

## Dynamic programming characteristics

Standard dynamic programming generally includes the following three characteristics

```
-Overlapping subproblem: there are repeated calculations in the enumeration process (such as recursive implementation of Fibonacci sequence)
-Optimal substructure: subproblems must be independent of each other, and subsequent calculations can be derived from the previous state
-No aftereffect: the dependence between subproblems is unidirectional, and the determined state will not be affected by subsequent decisions
```

## General dynamic programming problem solving framework

The core of dynamic programming is**State transition equation**, the following points need to be determined

```
-State (state parameter): the quantity (state variable) that will change between the sub problem and the original problem
-State storage memo: define the meaning of DP [i]... [J] according to the state parameters
-Initialization status: it is necessary to start the calculation of the "origin" (from the calculated subproblem to the larger problem)
-Decision making and state transition: the behavior of changing the state and making the state continuously approach the initialization state
```

The above is the overall idea to solve dynamic planning. If you want to use it flexibly, you also need to be proficient in various classic dynamic planning problems. See the classification list

## references

- https://time.geekbang.org/col…
- https://leetcode-cn.com/probl…
- https://github.com/shanejix/a…
- https://github.com/shanejix/a…