【动态规划算法】不同路径_不同路径升级版

//动态规划五步曲：
//1.确定dp[i][j] 的含义：
//到达dp[i][j] 位置一共有多少种不同路径
//2.确定递推公式
//dp[i][j] = dp[i-1][j] + dp[i][j-1];
//到dp[i-1][i]的路径量+到dp[i][j-1]的路径量。
//3.确定如何初始化
//最左边一行和最上边一行全部初始化成1，因为题目要求只能向下或者向右移动一步最上边一行到任意位置只有一种路径，最左边一行到任意位置也只有一种路径。
//4.确定遍历顺序，由题意可知，只能从左到右，从上到下进行遍历。
//5.打印dp数组的值
class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        int dp[m][n];
        for(int i = 0;i<m;++i)
        {
            dp[i][0] = 1;
        }
        for(int j = 0;j<n;++j)
        {
            dp[0][j] = 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];
                printf("%d ",dp[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
};

//初始化有障碍物，遇到障碍物及其之后的位置不能再初始化成1了，就跳过
for(int i = 0;i < m && obstacleGrid[i][0] != 1;++i)
{
    dp[i][0] = 1;
}
for(int j = 0;j<n && obstacleGrid[0][j] != 1;++j)
{
    dp[0][j] = 1;
}

for(int i = 1;i<m;++i)
        {
            for(int j = 1;j<n;++j)
            {
                if(obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

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));
        //初始化有障碍物，遇到障碍物及其之后的位置不能再初始化成1了，就跳过
        for(int i = 0;i < m && obstacleGrid[i][0] != 1;++i)
        {
            dp[i][0] = 1;
        }
        for(int j = 0;j<n && obstacleGrid[0][j] != 1;++j)
        {
            dp[0][j] = 1;
        }
        for(int i = 1;i<m;++i)
        {
            for(int j = 1;j<n;++j)
            {
                if(obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};