【动态规划】路径问题

1.不同路径1️⃣

1.题目连接

• 不同路径

2.算法原理讲解&&代码实现

• 动态规划–二维数组dp表
  • 线性表示：
    • dp[i][j]:到达[i][j]位置一共有多少种选择。
  • 状态转移方程
    • dp[i][j]=dp[i-1][j] dp[i][j-1]

---

代码语言：javascript复制

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m 1,vector<int>(n 1));
        dp[0][1]=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][n];

    }
};

1.不同路径2️⃣

1.题目连接

• 不同路径

2.算法原理讲解&&代码实现

• 动态规划–二维数组dp表
  • 线性表示：
    • dp[i][j]:到达[i][j]位置一共有多少种选择。
  • 状态转移方程
    • dp[i][j]=dp[i-1][j] dp[i][j-1] 但是不同之处为：当有障碍物时，该位置为0

代码语言：javascript复制

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) 
    {
        int m=ob.size();
        int n=ob[0].size();
        vector<vector<int>> dp(m 1,vector<int>(n 1));

        dp[0][1]=1;
        for(int i=1;i<=m;i  )
        {
            for(int j=1;j<=n;i  )
            {
                if(ob[i-1][j-1]==0)
                {
                    dp[i][j]=dp[i-1][j] dp[i][j-1];
                }
                else
                {
                    dp[i][j]=0;
                }

            }
           
        } 
        return dp[m][n];
    }
};

dp 动态规划 连接 数组 算法

0 人点赞