首页 > 代码库 > 动态规划第六讲——leetcode上的动态规划汇总(下)
动态规划第六讲——leetcode上的动态规划汇总(下)
接下来的几道题,都是有关路径问题,这可以说是DP问题的一种典型应用。路径有一个维度的;也有两个维度的。
Eg10:Climbing Stairs
这道题目比较简单,重在分析思路。
分析:略
class Solution { public: int minPathSum(vector<vector<int> > &grid) { int row, col; row=grid.size(); if(row==0) return -1; col=grid[0].size(); int i,j; for(j=1;j<col;j++) grid[0][j]+=grid[0][j-1]; for(i=1;i<row;i++){ grid[i][0]+=grid[i-1][0]; } for(i=1;i<row;i++){ for(j=1;j<col;j++){ grid[i][j] += min(grid[i-1][j],grid[i][j-1]); } } return grid[row-1][col-1]; } };
Eg12:Unique Paths
class Solution { public: int uniquePaths(int m, int n) { if(m<1 || n<1){ return 0; } int a[m][n]; int i,j; fill(a[0], a[0]+n, 1); for(j=1;j<m;j++) a[j][0]=1; for(i=1;i<m;i++) for(j=1;j<n;j++) a[i][j]=a[i-1][j] + a[i][j-1]; return a[m-1][n-1]; } };
Eg13:Unique Paths II
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { int m, n; m=obstacleGrid.size(); if(m==0) return 0; n=obstacleGrid[0].size(); if(n==0) return 0; int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) if(obstacleGrid[i][j]==1) obstacleGrid[i][j]=-1; for(j=0;j<n;j++) if(obstacleGrid[0][j]==0) obstacleGrid[0][j]=1; else if(obstacleGrid[0][j]==-1) break; for (i = 0; i < m; ++i){ if(obstacleGrid[i][0]==0) obstacleGrid[i][0]=1; else if(obstacleGrid[i][0]==-1) break; } for(i=1;i<m;i++){ for(j=1;j<n;j++){ if(obstacleGrid[i][j]!=-1) obstacleGrid[i][j]=obstacleGrid[i-1][j]*(obstacleGrid[i-1][j]>0? 1:0) + obstacleGrid[i][j-1]*(obstacleGrid[i][j-1]>0? 1:0); } } return obstacleGrid[m-1][n-1]>=0? obstacleGrid[m-1][n-1]:0; } };
Eg14:Jump Game
分析:这道题目与其说是DP,不如说是GA(贪心算法)。是的,这里又隐含一条我们以后要谈到的规律:谈心算法实际上是DP问题的加强版,每一个GA都可以用DP求解,反之不然。
我们仍然记得,DP问题的递推表达式类似:dp[i][j]= max{****};如果对max内部包含的时间复杂度是O(n)或者O(i)、O(j)的大小;那么此时如果贪心算法能够使用,往往需要O(1)的算法即可。
分析二:如果使用DP,对本题而言,dp[i] ||= {dp[j]&&(j+A[j]>=i)}
但是,这样毕竟有些浪费,比如对于{1, 2, 3, 4, 5}很明显到i的时候,可以忽略前面部分的i-2部分的计算结果,都可以合并到i-1之中,于是就有了GA:
class Solution { public: bool canJump(int A[], int n) { if(n<2) return true; int maxi = A[0]; int i; for (i = 1; i < n; ++i){ if(maxi > 0){ maxi --; maxi = max(maxi, A[i]) ; } else return false; } return true; } };
Eg15:Jump Game II
本题和上题目类似,代码如下:
class Solution { public: int jump(int A[], int n) { if(n<2) return 0; int maxi=A[0] , step_left =0, res=0; for (int i = 1; i < n; ++i){ if(maxi > 0){ if(step_left > 0){ step_left--; } else{ res++; step_left = maxi-1; } maxi --; maxi = max(maxi, A[i]); } else return -1; } return res; } };
Eg16:Wildcard Matching
dp[i+1][j+1]:s(0, i), t(0, j)是否能够匹配,res=dp[m][n];
递推关系就不写在这里了,这是一个2个方向的递归问题,需要注意的是时间和空间复杂度都是O(m*n), 因为实际测试的规模m, n在10^5, 所以没法通过。细细思考,有很多计算是不必要的;
计算dp[i+1][j+1], 仅仅需要dp[i][j+1], dp[i+1][j], dp[i][j].另外,如果是s="aaaaaaaaaa" t="aaaaaaaaaaaaaaaaaaa*"那么,我们计算dp[10][j],如果上一行左侧元素全部是0, 本行在0之前的计算都是冗余的。也就是说,我们仅仅需要从上一行不是0的地方开始算起。例如,上面的例子,dp[1][1]=true, dp[1][2]=false之后的dp[1][j]=false 是一直成立的。这样,这个问题就变成了一个回溯问题,见下面的代码。所以,这类求解存在性而非最优化的题目,使用DP往往不是最优的解法。 下面的这个解法,本质上是贪心算法,就是让固定长度的s匹配最长的t;如果失败,那么回溯到上一个*所在的位置。
class Solution { public: bool isMatch(const char *s, const char *p) { const char *prevs=s, *prev_start=NULL; while(*s){ if(*p=='?' || *p==*s){p++;s++;continue;} if(*p == '*') {prev_start=p; p++; prevs=s;continue;} if(prev_start) {p=prev_start+1; s= prevs+1;prevs++;continue;} return false; } while((*p)=='*') p++; return !(*p); } }; <span style="font-size:14px;"> </span>
需要注意的是,在这种模式下,"abc" 与 "a*"是匹配的。
动态规划第六讲——leetcode上的动态规划汇总(下)