动态规划2

1.不同路径

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

第一反应是动态规划，尝试用dfs果然超时了。。。。。。

class Solution {
public:
    const int dx[2]={1,0};
    const int dy[2]={0,-1};
    int sum=0;
    void dfs(int x,int y,int m,int n)
    {
        if (x == m - 1 && y == n - 1)
        {
            sum++;  
            return;
        }
        // 向下移动
        if (x + 1 < m) 
        {
            dfs(x + 1, y, m, n);
        }
        // 向右移动
        if (y + 1 < n) 
        {
            dfs(x, y + 1, m, n);
        }
    }
    int uniquePaths(int m, int n) {
        dfs(0,0,m,n);
        return sum;
    }
};

 正确方法：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,1));//到(i,j)的不同路径数
        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                //dp[i][j]=上方位置可达总共的路径数+左方位置可达总共的路径数
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

2.不同路径Ⅱ

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

class Solution
{
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int rows = obstacleGrid.size();
int cols = obstacleGrid[0].size();
// 如果起点或终点有障碍物，直接返回 0
if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1)
{
return 0;
}
// 创建dp数组并初始化
vector<vector<int>> dp(rows, vector<int>(cols, 0));
// 初始化起点
dp[0][0] = 1;
// 初始化第
for (int i = 1; i < rows; i++)
{
if (obstacleGrid[i][0] == 1)
{
dp[i][0] = 0;  // 如果有障碍物，之后的位置都不可达
}
else
{
dp[i][0] = dp[i - 1][0];
}
}
// 初始化第一行
for (int j = 1; j < cols; j++)
{
if (obstacleGrid[0][j] == 1)
{
dp[0][j] = 0;  // 如果有障碍物，之后的位置都不可达
}
else
{
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
if (obstacleGrid[i][j] == 1)
{
dp[i][j] = 0;  // 障碍物位置的路径数为0
}
else
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[rows - 1][cols - 1];
}
};

3.最小路径和 

题目链接：64. 最小路径和 - 力扣（LeetCode）

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
int cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        dp[0][0]=grid[0][0];
        //初始化前缀数字和
        for (int i = 1; i < rows; i++) 
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < cols; j++) 
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++)
{
    for (int j = 1; j < cols; j++)
            {
                dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
            }
}
return dp[rows-1][cols-1];
    }
};

原文地址：https://blog.csdn.net/2301_77869606/article/details/142531262

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！