20250208力扣每日一题

知识点

二维数组的初始化：

vector<vector<int>> dp(m, vector<int>(n, 0));

解题思路

使用动态规划解决这道问题，首先构建dp数组，记录到当前这一点有多少条路径
接下来构建状态转移方程，公式如下

\[f(i,j) = \left\{ \begin{array}{cl} 0 & i=0 \text{ or }j=0 \\ f(i-1,j)+f(i,j-1) & i\geq1,j\geq1 \end{array} \right.\]

当遇到障碍物时，遍历节点不用做任何更改，跳过当前循环即可，这样保证状态转移方程对于没有障碍物的结点是合理的
如果没有遇到障碍物，则利用状态转移方程进行计算

实现代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> directions = {{0, 1}, {1, 0}};

        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])
                break;
            dp[i][0] = 1;
        }

        for(int i = 0; i < n; i ++){
            if(obstacleGrid[0][i])
                break;
            dp[0][i] = 1;
        }

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

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

知识点

解题思路

实现代码

Enjoy Reading This Article?