首先要判断一道题是否是动态规划
- 一般动态规划是求最值（但也不是百分之百）
- 最优子结构
一般会通过子问题的最值得到原问题的答案 - 穷举
- 状态转移方程
- 重叠 子问题
由于暴力求解效率低，所以需要备忘录或者DP table来优化穷举过程
下面是重点，思维框架
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
以coinChange为例
- base case
- 状态（也就是变量）
原问题和子问题中变化的变量（目标金额amount，因为目标金额会不断的向最终结果靠近） - 选择，也就是导致状态产生变化的行为
目标金额为什么会变化呢，因为在选择硬币，没选择一枚硬币，金额就更靠近我们的目标金额。所以所有硬币的面值就是选择。 - 确定dp函数/dp数组的定义
自顶向下，一般自顶向下的解法是一个递归的dp函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说的状态，函数的返回值就是题目要求我们的计算的量，
function coinChange (coins, amount) {
const memo = [];
function dp (n) {
if (n === 0) return 0;
if (n < 0) return -1;
if (memo[n] !== undefined) return memo[n];
let res = Infinity;
for (const coin of coins) {
const sub = dp(n - coin);
memo[n - coin] = sub;
if (sub === -1) continue;
res = Math.min(res, sub + 1);
}
if (res === Infinity) return -1;
return res;
}
return dp(amount);
}
function coinChange (coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let n = 0; n < amount+1; n++ ) {
for (const coin of coins) {
if (n - coin < 0) continue;
dp[n] = Math.min(dp[n], dp[n - coin] + 1);
}
}
return (dp[amount] === amount + 1) ? -1 : dp[amount];
}
