动态规划入门
动态规划题目特点
-
计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是Sum
-
求最大值最小值
- 从左上角走到右下角路径的最大数字和
- 最长上升序列长度
-
求存在性
- 取石子游戏， 先手是否必胜
- 能不能选出k个数使得和是Sum
解题步骤
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
计算顺序
从小到大，一个for循环搞定
/**
*
* @param {int []} A
* @param {int} M
*/
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
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){
if(i >= A[j] && f[i - A[j]] != Number.MAX_VALUE){
var a = f[i - A[j]] + 1;
var b = f[i];
f[i] = Math.min.apply(null, [a, b])
}
}
}
if(f[M] == Number.MAX_VALUE){
return -1;
}
return f[M]
}
小结
求最值规划组成的部分：
-
确定状态
- 最后一步（最优策略中使用的最后一枚硬币ak）
- 化成子问题（最少的硬币拼出更小的面值27-ak）
-
转移方程
- f【x】 = min{ f【x-2】+1， f【x-5】+1， f【x-7】+1 }
-
初始条件和边界情况
- f【0】= 0，如果不能拼出Y， f【Y】 = 正无穷
-
计算顺序
- f【0】，f【1】，f【2】。。。。， 因为计算f【2】时需要f【1】f【0】都计算完毕
动态规划：
消除冗余， 加速计算
计数型动态规划
题目二
给定m行n列的网格， 有一个机器人从左上角（0,0）出发， 每一步可以向下或者向右走一步。
问有多少种不同的方式走到右下角。
确定状态
最后一步： 无论机器人用何种方式到达右下角， 总有最后挪动的一步： 向右或者向下
右下角坐标设为（m-1, n-1）
那么前一步机器人一定是在（m-2，n-1）或者（m-1, n-2）
子问题：
那么， 如果机器人有x种方式从左上角走到（m-2，n-1），有Y种方式从左上角走到（m-1，n-2），则机器人有x+y种方式走到（m-1，n-1）
问题转化为：
机器人有多少种方式从左上角走到（m-2，n-1）和（m-1，n-2）
原题要求有多少方式从左上角走到（m-1，n-1）
状态：
设f【i】【j】为机器人有多少种方式从左上角走到（i，j）
对于任意一个格子（i，j）
f【i】【j】=f【i-1】【j】 + f【i】f【j-1】
机器人有多少种方式走到（i，j） = 机器人有多少种方式走到（i-1，j） + 机器人有多少种方式走到（i，j-1）
初始条件和边界情况
初始条件：f【0】【0】=1，因为机器人只有一种方式到左上角
边界情况：i = 0 或 j = 0， 则前一步只能有一个方向过来->f【i】【j】= 1
计算顺序
f【0】【0】 = 1
计算第0行： f【0】【0】， f【0】【1】
答案是f【m-1】【n-1】
代码
function uniquePaths(m, n) {
var f = new Array(m);
f.fill(new Array(n).fill(0, 0), 0);
var i, j;
for (i = 0; i < m; ++i) {
// row
for (j = 0; j < n; ++j) {
// column
if (i == 0 || j == 0) {
f[i][j] = 1;
} else {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
}
存在性动态规划
青蛙跳石头
有n块石头分别在x轴的0， 1， 。。。n-1位置
一只青蛙在石头0， 想跳到石头n-1
如果青蛙在第i块石头上，他最多可以向右跳距离ai
问青蛙能否跳到石头n-1
例子
- 输入： a=【2，3，1，1，4】
- 输出： True
- 输入： a=【3，2，1，0，4】
- 输出： False
确定状态
- 最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步
- 这一步是从石头i跳过来， i < n -1
这需要两个条件同时满足
- 青蛙可以跳到石头i
- 最后一步不超过跳跃的最大距离： n - 1 -i <= ai
子问题
状态： 设f【j】表示青蛙能不能跳到石头j
f【j】= OR（f【i】AND i + a【i】>= j）
0 <= i < j: 枚举上一个跳到的石头i
f【i】： 青蛙能不能跳到石头i
i + a【i】>= j：最后一步的距离不能超过ai
初始条件和边界情况
初始条件： f【0】 = True， 因为青蛙一开始就在石头0
没有边界情况： 因为枚举不存在越界情况
计算顺序
从左到右
答案是f【n-1】
时间复炸度：O（N^2），空间复杂度数组大小：O（N）
代码
function conJump(A) {
var n = A.length;
f = new Array(n);
f[0] = true;
var i, j;
for (j = 1; j < n; ++j) {
f[j] = false;
for (i = 0; i < j; ++i) {
if (f[i] && i + A[i] >= j) {
f[j] = true;
break;
}
}
}
return f[n - 1];
}
var r1 = conJump([2, 3, 1, 1, 4]);
var r2 = conJump([3, 2, 1, 0, 4]);
console.log(r1);
console.log(r2);
动态规划入门总结
四个组成部分
确定状态
- 研究最优策略的最后一步
- 化为子问题
转移方程
- 根据子问题定义直接得到
初始条件和边界情况
- 细心，考虑周全
计算顺序
- 利用之前的计算结果