遇到动态规划的一般解题思路：
1. 确定步骤
状态在动态规划中的作用属于定海神针。
简单来说， 解动态规划的时候需要开一个数组， 数组的每个元素f【i】或者f【i】【j】代表什么
确定状态需要两个意识：
- 最后一步
- 子问题
2. 转移方程
f【x】 = f【x-1】
3. 初始化条件和边界情况
初始条件， 用转移方程算不出来， 需要手动定义
边界情况， 数组不要越界，向上越界，向下越界
4. 计算顺序
当我们计算到f【x】时， 右边的都已经得到结果了
举个例子：
- 你有三种硬币， 分别面值2元， 5元和7元， 每种硬币都有足够多
- 买一本书需要27元
- 如何用最少的硬币组合正好付清， 不需要对方找钱
拆分：
最后一步
虽然我们不知道最优策略是什么， 但是最优策略肯定是K枚硬币a1, a2... ak面值加起来是27
所以一定有一枚最后的硬币：ak
除掉这枚硬币， 前面的面值加起来是27 - ak
关键点
我们不关心前面的K-1枚硬币是怎么拼出27-ak的（可能有一种拼法， 可能有100中拼法）， 而且我们现在甚至还不知道ak和K， 但是我们确定前面的硬币拼出了27-ak
因为是最优策略， 所以拼出27-ak的硬币数一定要最少， 否则这就不是最优策略了
子问题
所以我们就要求： 最少用多少枚硬币可以拼出27-ak
原问题是最少用多少问题拼出27
我们将原问题转化成了一个子问题， 而且规模更小： 27-ak
为了简化定义， 我们设状态f（x） = 最少用多少枚硬币拼出x
等等，我们还不知道最后那一枚硬币ak是多少
最后那枚硬币ak只可能是2，5或者7
如果ak是2，f（27）应该是f（27-2）+1（加上最后这一枚硬币2）
如果ak是5，f（27）应该是f（27-5）+1（加上最后这一枚硬币5）
如果ak是7，f（27）应该是f（27-7）+1（加上最后这一枚硬币7）
除此之外， 没有其他的可能了
需要求最少的硬币数，所以：
f(27) = min(f(27-2)+1, f(27-5)+1, f(27-7)+1)
转移方程
设状态f【X】=最少用多少枚硬币拼出X
对于任意X
f【x】= min{ f【x-2】+1， f【x-5】+1， f【x-7】+1 }
初始化条件和边界情况
f【x】= min{ f【x-2】+1， f【x-5】+1， f【x-7】+1 }
两个问题
- x-2，x-5或者x-7小于0怎么办？
- 什么时候停下来
如果不能拼出Y，就定义f【Y】=正无穷， 例如f【-1】=f【-2】 = 。。。 = 正无穷
所以f【1】 = min【f【-1】+1，f【-4】+1， f【-6】+1】 = 正无穷， 表示拼不出来1
初始条件： f【0】= 0
function coinChange(A, M){
var f = new Array(M+1);
// f.fill(0,0, f.length) // 用0初始化数组
var n = A.length // number of kinds of coins
// initialization
// console.log(Number.MAX_VALUE)
f[0] = 0;
var i, j;
// f[1], f[2], .... f[27]
for(i = 1; i <= M; ++i){
f[i] = Number.MAX_VALUE;//某一个是正无穷
// last coin a[j]
for(j = 0; j <= n; ++j){ //j是硬币类型
if(i >= A[j] && f[i - A[j]] != Number.MAX_VALUE){ //A[j]是最后一枚硬币面额
var a = f[i - A[j]] + 1;//递归
var b = f[i];//递归
f[i] = Math.min.apply(null, [a, b])
}
}
}
console.log(f)
if(f[M] == Number.MAX_VALUE){
return -1;
}
return f[M]
}
console.log(coinChange([2, 5, 7], 27));
长风破浪会有时，直挂云帆济沧海