当前位置：首页 > article >正文

刷爆leetccode Day7 DP

article 2024/10/23 23:01:33

DP

6. 不同路径II（medium）
7. 礼物的最大价值（medium）
8. 下降路径最小和（medium）
9. 最小路径和（medium）
10. 地下城游戏（hard）

6. 不同路径II（medium）

题目

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //该位置为障碍物时，dp表中该位置为0
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>>dp((m+1),vector<int>(n+1));
        dp[0][1]=1;
        for(int i=1;i<m+1;i++)
        {
            for(int j=1;j<n+1;j++)
            if(obstacleGrid[i-1][j-1]==0)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
        return dp[m][n];
    }
};

7. 礼物的最大价值（medium）

题目

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m=frame.size();
        int n=frame[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<m+1;i++)
        {
            for(int j=1;j<n+1;j++)
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
        }
        return dp[m][n];
    }
};

8. 下降路径最小和（medium）

题目


class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        const int matrix_max=INT_MAX;
        int m=matrix.size();
        vector<vector<int>> dp(m+1,vector<int>(m+2,matrix_max));
        for(int k=0;k<m+2;k++)
        dp[0][k]=0;
        for(int i=1;i<m+1;i++)
        {
            for(int j=1;j<m+1;j++)
            dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];
        }
        int ret=dp[m][1];
        for(int l=1;l<m+1;l++)
        {
            ret=min(ret,dp[m][l]);
        }
        return ret;
    }
};

9. 最小路径和（medium）

题目

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][1]=0;
        for(int i=1;i<m+1;i++)
        {
            for(int j=1;j<n+1;j++)
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
        }
        return dp[m][n];
    }
};

10. 地下城游戏（hard）

题目

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m=dungeon.size();
        int n=dungeon[0].size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
        dp[m-1][n]=dp[m][n-1]=1;
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=max(1,dp[i][j]);//防止出现该位置最低血量为负数的情况
            }
        }
        return dp[0][0];
    }
};