题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
动态规划
题目问总共有多少条不同的路径?所以dp[i][j]表示到达(i,j)点时的路径条数;
dp[i][j]=dp[i-1][j]+dp[i][j-1] 所以到达该点的路径等于左边点的路径+上边点的路径和
需要注意的是左边界和右边界,路径只有一条
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(2, vector<int>(n,0)); for(int i=0;i<m;i++)//从0开始的,所以到m-1结束 dp[i][0]=1; for(int i=0;i<n;i++) dp[0][i]=1; for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } };
优化
具体参考leetcode题解
对于每个点,只需要知道该行和上一行就可以了,所以只留下两行
第三行的时候覆盖第一行,次数所需要的的上一点的数据就变成了了下一点,所以(i-1)%2 取余 使得结果都在这两行内
交替使用
程序上也就是把前一个程序的所以行i变成了i%2 i-1变成(i-1)%2
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(2, vector<int>(n,0)); for(int i=0;i<m;i++) dp[i%2][0]=1; for(int i=0;i<n;i++) dp[0][i]=1; for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i%2][j]=dp[(i-1)%2][j]+dp[i%2][j-1]; } } return dp[(m-1)%2][n-1]; } };
不同路径Ⅱ
现在考虑网格中有障碍物。网格中的障碍物和空位置分别用 1 和 0 来表示。
思路:
有炸弹的话,表示当前的路是不可行的,走不通的
所以加一种情况
不为炸弹时:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
为炸弹时:dp[i][j] = 0
可以将二维数组初始化为全0,只有非炸弹情况才填充
注意:::对于最上一行和最左一列,如果出现一个炸弹,后面全为0!!!!!!
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m; i++) { if (obstacleGrid[i][0] == 1) //如有一个炸弹,下边全都不能走 break; else dp[i][0] = 1; } for (int j = 0; j < n; j++) { if (obstacleGrid[0][j] == 1) //如有一个炸弹,后边全都不能走 break; else dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] != 1) //非炸弹才计算,是炸弹时默认0 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } };