10｜面试即正义第二期：常见的动态规划面试题串烧

带障碍的可行性那个题目在leetcode上要求打出路径，补一个带路劲的c++代码给有需要的小伙伴 //leetcode:面试题 08.02. 迷路的机器人 class Solution { public: vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) { // 判断边界条件 vector<vector<int>> res; int row = obstacleGrid.size(); if(!row) return res; int col = obstacleGrid[0].size(); if(!col) return res; if(obstacleGrid[0][0] == 1 || obstacleGrid[row -1][col -1] == 1) return res; // 初始化边界条件 int dp[row][col];memset(dp,0,sizeof(dp)); dp[row-1][col-1] = 1; for(int i{row-2} ; i>=0;i--) {//初始化最后一列 if(obstacleGrid[i][col-1] == 1) dp[i][col-1] = 0; else dp[i][col-1] = dp[i+1][col-1]; } for(int i{col-2};i>=0;i--) {//初始化最后一行 if(obstacleGrid[row-1][i] == 1) dp[row-1][i] = 0; else dp[row-1][i] = dp[row-1][i+1]; } //求路径 for(int i{row-2};i>=0;--i) { for(int j{col-2}; j>=0 ;--j) { if(obstacleGrid[i][j] == 1) dp[i][j] = 0; else dp[i][j] = max(dp[i+1][j],dp[i][j+1]); } } if(dp[0][0] == 0) return res; int r{0},c{0}; while(r != row-1 || c != col-1) { res.push_back({r,c}); int down{0};//内部变量不会默认初始化C++，一定要小心 if(r < row-1) down = dp[r+1][c]; int right{0}; if(c < col-1) right = dp[r][c+1]; if(down >= right) r++; else c++; } res.push_back({row-1,col-1}); return res; } }; 话说回来，感觉老师这个专利每篇质量不一啊，大部分都挺好，但背包问题那两讲，图画的有问题，备忘录，重叠子问题部分描述的有些晦涩，劝退了好多小伙伴啊，感觉把那两章重新写一哈，这个专栏的价值能翻一倍

跳跃游戏题目，我尝试了一下只用一层for循环，dp[i]保存的是所能达到的最远位置，每次需要先判断一下可达的最远位置是否能够到当前位置。 def canJump(arr): dp = [0 for _ in range(len(arr))] dp[0] = arr[0] for i in range(1, len(arr)): if dp[i-1] < i: return False dp[i] = max(dp[i-1], i + arr[i]) return True

带障碍物的不同路径中，初始化操作除了（0，0）位置是根据数组值进行判断，其他应该是根据上一个dp值进行判断吧。比如（0，1）位置是障碍物，那么（0，2）肯定就是0。因为没办法通过（0，0）走到（0，2）

为何不试试逆序遍历呢 func JumpGame(arr []int) bool { index := len(arr) - 1 for i := index - 1; i >= 0; i-- { if i+arr[i] >= index { index = i } } if index == 0 { return true } return false }

有障碍物的路径问题，老师的java版代码应该是有问题的，在leetcode上提交是失败的，在初始化那块有点问题，第一列只要存在障碍物，应该直接break出循环，第一行的初始化也一样 public int uniquePathsWithObstacles(int[][] obstacleGrid) { // 行数 int m = obstacleGrid.length; // 列数 int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; // 初始化状态 for(int i = 0; i < m; i++) { dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : 1; // 第一列只要出现障碍物，下面的肯定是0 if(obstacleGrid[i][0] == 1) { break; } } for(int j = 0; j < n; j++) { dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : 1; // 第一行只要出现障碍物，后面的肯定是0 if(obstacleGrid[0][j] == 1) { break; } } // 状态转移方程 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; }

二刷，都是自己独立思考递推公式，找到感觉了，非常赞的专栏

第一个老数学题了， 机器人一定会走 m + n - 2 步，其中有 n - 1步往下走。 所以结果C((m+n-2), (n-1))。 不过计算组合数可能溢出，dp算是大数求组合数的防溢出方案吧。

带障碍的路径问题中，初始状态，对应第一行或者第一列，出现一个障碍后，后面的路径是不是都应该为0，而不是只有障碍的地方是0？

//v[i][j] - i为行，j为列，值为0时表示此路不通，大于0时表示从上方或左方到达此点的长度 // 0 <= i,j < 1000 //0 <= v[i][j] < 1000 int getMaxPathLenWithBlocks(int[][] v) { int m = v.length; int n = v[0].length; int[][] dp = new int[m][n]; // 初始化状态 for (int i = 0; i < m; i ++) { dp[i][0] = v[i][0] == 0 ? 0 : i > 0 ? dp[i-1][0] + v[i][0]: v[i][0]; } for (int j = 0; j < n; j ++) { dp[0][j] = v[0][j] == 0 ? 0 : j > 0 ? dp[0][j-1] + v[0][j]: v[0][j]; } for (int i = 1; i < m; i ++) { // 状态转移过程 for (int j = 1; j < n; j ++) { if (v[i][j] == 0) { dp[i][j] = 0; } else { dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]) + v[i][j]; } } } return dp[m - 1][n - 1]; // 输出答案 }