动态规划算法

题目：给定一个矩阵网络，一个机器人从左上角出发，每次可以向下或向右走一步 A:求有多少钟方式走到右下角（动态规划） B:输出所有走到右下角的路径（递归）

动态规划题目特点：

1.计数

有多少种方式走到右下角有多少种方法选出k个数使得和是sum

2.求最大最小值

从左上角走到右下角路径的最大数字和最长上升子序列长度 Leetcode300 10

3.求存在性

取石子游戏，先手是否必胜能不能选出k个数使得和是sum

例题

你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多

买一本书需要27元如何用最少的硬币组合正好付清，不需要对象找钱（求最大最小值）

动态规划组成部分一：确定状态

解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么

类似于解数学题中x,y,z代表什么最后一步

最后一步

keyOne: 我们不关心前面的k-1枚硬币是怎么拼出27-ak的（可能有1种拼法，可能有100种拼法），而且我们现在甚至还不知道ak和k,但是我们确定前面的硬币拼出27-ak。

keyTwo:因为是最优策略，所以拼出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} int f(int x ){ //f(x)=最少用多少枚硬币拼出x if(x==0) return 0; //0元钱只要0枚硬币 int res = MAX_VALUE; //初始化用无穷大 if(x>=2){ //最后一枚硬币是2元 res = Math.min(f(x-2)+1,res); } if(x>=5){ //最后一枚硬币是5元 res = Math.min(f(x-5)+1,res); } if(x>=7){ //最后一枚硬币是7元 res = Math.min(f(x-7)+1,res); } return res; }

递归解法的问题：

做了很多重复计算，效率低下如何避免？将计算结果保存下来，并改变计算顺序

动态规划组成部分二： 转移方程

设状态f[x]=最少用多少枚硬币拼出X对于任意X F(27)=min{F(27-2)+1,F(27-5)+1,F(27-7)+1}

动态规划组成部分三：初始条件和边界情况

F(27)=min{F(27-2)+1,F(27-5)+1,F(27-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

动态规划组成部分四：计算顺序

拼出x所需要的最少硬币数：f[X] = min{f[X-2]+1,f[X-5]+1,f[X-7]+1}初始条件：f[0]=0然后计算f[1],f[2],…f[27]当我们计算到f[X]时，f[X-2],f[X-5],f[X-7]都已经得到结果了每一步尝试三种硬币，一共27步与递归算法相比，没有任何重复计算算法时间复杂度（即需要进行的步数）：27*3

代码

class Solution { public int coinChange(int[] A,int M) { int[] f = new int[M+1]; int n = A.length; //initialization f[0]=0; int i,j; //f[1],f[2],...f[27] for (i=1;i<=M;++i){ f[i]=Integer.MAX_VALUE; //last coin A[j] //f[i] = min{f[i-A[0]]+1,...,f[i-A[n-1]]+1} for(j=0;j<n;++j){ if(i>=A[j]&&f[i-A[j]]!=Integer.MAX_VALUE){ f[i] = Math.min(f[i-A[j]]+1,f[i]); } } } if(f[M]==Integer.MAX_VALUE){ f[M]=-1; } return f[M]; } }

例题

给定一个矩阵网络，一个机器人从左上角出发，每次可以向下或向右走一步 求有多少钟方式走到右下角（动态规划）

class Solution { public int unique(int m,int n) { int[][] f =new int[m][n]; int i,j; for(i=0;i<m;++i){ //row:top to bottom for(j=0;j<n;++j){ //colum: left to right if(i==0||j==0){ f[i][j]=1; } else { f[i][j]=f[i][j-1]+f[i-1][j]; } } } 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]

输出：Fasle

动态规划组成部分一：确定状态

最后一步：如果青蛙能跳到最后一块石头n-1,我们考虑它跳的最后一步这一步是从石头i跳过来，i<n-1这需要两个条件同时满足：1）青蛙可以跳到石头i 2)最后一步不超过跳跃的最大距离：n-1-i<=ai

子问题

那么，我们需要知道青蛙能不能跳到石头i(i<n-1)而我们原来要求青蛙能不能跳到石头n-1子问题状态：设f[j]表示青蛙能不能跳到石头j

动态规划组成部分二：转移方程

动态规划组成部分三：初始条件和边界情况

设f[j]表示青蛙能不能跳到石头j初始条件：f[0]=True,因为青蛙一开始就在石头0 class Solution { public Boolean canJump(int[] A) { int n = A.length; boolean[] f = new boolean[n]; f[0]=true;//initialization for(int j=1;j<n;++j){ f[j] = false; //previous stone i //last jump is from i to j for(int i=0;i<j;++i){ if(f[i]&&i+A[i]>=j){ f[j]=true; break; } } } return f[n-1]; } }