62.不同路径
思路
本题同样为因果问题，位置n一定是两种情况导致dp[i][j] = dp[i-1][j]+dp[i][j-1]故使用动态规划。
难点在于如何初始化，在递推公式中出现了i-1、j-1等，所以循环需要从1开始,而dp需要遍历m×n全部情况，所以初始化第一行、第一列。
本题因为约束极少，可以视作排列组合问题，重点关注排列组合中越界问题以及整体代码编写思路。
一维dp解法待补充······
题解
class Solution {
public:
int uniquePaths(int m, int n) {
// vector<vector<int>> dp(m, vector<int>(n,0));
// for(int i = 0;i<m;i++)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];
int count = m-1;
long long up = 1;
int div = m-1;
int t = m+n-2;
while(count--)
{
up *= (t--);
while(div!=0 && up%div == 0)
{
up /= div;
div--;
}
}
return up;
}
};
63.不同路径II
思路
本题加了障碍物约束，递归与排列组合解法变得不在适用，仅可使用动态规划。
与上一题类似，注意判断障碍物即可，很简单。
一维dp解法待补充······
题解
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0));
for(int i = 0;i<obstacleGrid[0].size();i++)
{
if(obstacleGrid[0][i]!=1)dp[0][i] = 1;
else break;
}
for(int i = 0;i<obstacleGrid.size();i++)
{
if(obstacleGrid[i][0]!=1)dp[i][0] = 1;
else break;
}
for(int i = 1;i<obstacleGrid.size();i++)
{
for(int j = 1;j<obstacleGrid[0].size();j++)
{
if(obstacleGrid[i][j] == 1)dp[i][j] = 0;
else
{
dp[i][j] = dp[i-1][j]+ dp[i][j-1];
}
}
}
return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
}
};