动态规划 —— 路径问题-不同路径 ||

1. 不同路径 ||

题目链接： 63. 不同路径 II - 力扣（LeetCode）

https://leetcode.cn/problems/unique-paths-ii/description/

2. 算法原理

状态表示：以莫一个位置位置为结尾 dp[i，j]表示：走到[i，j]位置的时候一共有多少种方法

2. 状态转移方程 根据最近的一步来划分问题： 到达dp[i][j]有两种情况：1. dp[i][j]的位置有障碍物，0

2. dp[i][j]的位置没有障碍物,那么又分为两种情况： a. 从上面过来：dp[i-1，j] -> dp[i，j]，dp[i-1，j] b. 从左边过来：dp[i，j-1] -> dp[i，j]，dp[i，j-1] 本题的状态转移方程是：dp[i][j] = dp[i-1，j] + dp[i，j-1]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行 我们可以在上面的一行和左边的一列再额外的加上一行和一列的虚拟节点，虚拟位置为1是因为上面的值加上左边的值就可以得到原来第一个位置的值，再按照上面的值加上左边的值来计算其他位置的值

本题的下标映射关系：因为本题给了一个矩阵，而我们又额外的加上一行和一列的虚拟节点，所以我们的下标都统一往右下角移动了一位，如果想找回之前对应的位置，那么下标需要进行统一减1（横纵坐标）

但是如果我们vector里面不写初始化里面本来就是0，也就是说可以不用管里面有障碍物的情况

4. 填表顺序 本题的填表顺序是：从上往下填写每一行，每一行的值是从左往右

5. 返回值 ：题目要求 + 状态表示 本题的返回值是：dp[m][n]

3.代码

动态规划的固定四步骤：1. 创建一个dp表 2. 在填表之前初始化 3. 填表（填表方法：状态转移方程） 4. 确定返回值

public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        //定义横纵坐标
        int m=ob.size(),n=ob[0].size();
        //创建dp表二维数组
        //我们vector里面不写初始化里面本来就是0
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        //只用初始化[1][0]为1，其他会默认初始化为0
        dp[1][0]=1;
        //从上往下填写每一行，每一行的值是从左往右
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(ob[i-1][j-1]==0)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            
            return dp[m][n];


    }
};

完结撒花~