如何确定动态规划的转移方程
我流浪般的赤着双脚走来,
深感途程上顽石棱角的坚硬.
再加上那一丛丛拦路的荆棘,
使我每一步都留下一道血痕.
——食指:《热爱生命》1978
开篇点题
-
先观察最后一个状态
比如 LintCode 114 ,题意是从一个二维数组的左上角走到右下角共有多少种不同的路径.且每次只能向下或者向右走一步,最后一个状态就是右下角
2. 观察到达最后一个状态的前面的所有状态,它只能从该位置的上面或者右边过来,故前两个状态就是上面和右边的位置.
3. 写出动态转移方程: f[i][j] = f[i-1][j] + f[i][j-1],其中f[i][j]代表走到位置的所有情况种数.
4. 你没看错,那就是状态转移方程.
5. 之后确定边界条件,什么叫边界条件?
6. 比如左上角没有右边和上边,所以 f[0][0] = 1
第一列和第一行只有一种到达的方式,横着走或竖着走,依次+1即可
7. 反过来从 f[0][0]开始使用状态转移方程计算就可以了,比如f[1][1] = f[0][1] +f[1][0]
代码见下:
class Solution {public:int f[110][110];int solve(int m,int n){for(int i=0;i<m;++i) f[i][0]=1;for(int i=0;i<n;++i) f[0][i]=1;for(int i=1;i<m;++i){for(int j=1;j<n;++j){f[i][j]=f[i-1][j]+f[i][j-1];}}}/*** @param m: positive integer (1 <= m <= 100)* @param n: positive integer (1 <= n <= 100)* @return: An integer*/int uniquePaths(int m, int n) {// write your code herememset(f,0,sizeof(f));solve(m,n);return f[m-1][n-1];}};
状态在动态规划中的作用属于定海神针
简单地说,解决动态规划的时候需要开一个数组,数组的每个元素f[i]或者f[i][j]代表什么
类似于解数学题中,X,Y,Z代表什么
那么依赖什么来确定状态呢?
最后一步
子问题
so.什么是最后一步?
🤞举个栗子:
虽然我们不知道最优策略是什么,但是最优策略肯定是K枚硬币a1,a2...ak面值加起来为27
所以一定会有最后一枚硬币ak
除掉这枚硬币,前面的硬币的面值加起来是27-ak
...
TIP
关键点:
我们并不关心K-1枚硬币是怎么拼出27-ak的.我们甚至不知道ak和K.但是我们知道前面的硬币一定拼出了27-ak
因为是最优策略,所以27-ak的硬币数一定是最少的
所以我们可以这样来做: 最少用多少枚硬币可以拼出27-ak
故原问题转换成了一个子问题(
规模缩小): 27-ak为了简化定义,我们设状态f(X) = 最少用多少枚硬币拼出X
🎃但我们始终还不知道ak是啥???
最后那枚硬币只可能是2,5,7
若是2,则f(27) = f(27-2) + 1
若是5,则f(27) = f(27-5) + 1
若是7,则f(27) = f(27-7) + 1
最少的硬币数,则
f(27) = min{上面三个}
这道题如果用递归解法,会出现一个问题,即同样的子问题被计算了多次,所以为了解决这个问题,引入了记忆数组这玩意来剪枝