C++算法第十一天

本篇文章我们继续学习动态规划

目录

第一题

题目链接

题目解析

代码原理

代码编写

第二题

题目链接

题目解析

代码原理

代码编写

第三题

题目链接

题目解析

代码原理

代码编写

第四题

题目链接

题目解析

代码原理

代码编写

第五题

题目链接

题目解析

代码原理

代码编写

题后总结

---

第一题

题目链接

题目解析

代码原理

代码编写

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m = obstacleGrid.size(), n = obstacleGrid[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        //初始化

        dp[0][1] = 1;//当然这里dp[1][0] = 1也是可以的

        //填表

        for(int i = 1; i <= m; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                //状态转移方程

                if(obstacleGrid[i - 1][j - 1] == 0)

                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

            }

        }

        return dp[m][n];

    }

};

第二题

题目链接

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    int jewelleryValue(vector<vector<int>>& frame) {

        int m = frame.size(), n = frame[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        //初始化

        dp[0][1] = 0;

        //填表

        for(int i = 1; i <= m; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];

            }

        }

        return dp[m][n];

    }

};

第三题

题目链接

931. 下降路径最小和 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    int minFallingPathSum(vector<vector<int>>& matrix) {

        int n = matrix.size();

        //建表

        vector<vector<int>> dp(n + 1,vector<int>(n + 2, INT_MAX));

        //初始化第一行

        for(int j = 0; j < n + 2; j++)

        {

            dp[0][j] = 0;

        }

        //填表

        for(int i = 1; i < n + 1; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]),dp[i - 1][j + 1]) + matrix[i - 1][j - 1];

            }

        }

        int ret = INT_MAX;

        for(int j = 1; j <= n; j++)

        {

            ret = min(ret, dp[n][j]);

        }

        return ret;

    }

};

第四题

题目链接

64. 最小路径和 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        int m = grid.size(), 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; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + grid[i - 1][j - 1];

            }

        }

        return dp[m][n];

    }

};

第五题

题目链接

174. 地下城游戏 - 力扣（LeetCode）

题目解析

代码原理

这里的状态方程有个小错误需要注意一下，正确的我放在下面啦，别看漏哦

正确的状态转移方程：dp[i][j] = min(dp[i][j + 1],dp[i + 1][j]) - cur[i][j]

代码编写

class Solution {

public:

    int calculateMinimumHP(vector<vector<int>>& dungeon) {

        int m = dungeon.size(),n = dungeon[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        //初始化

        dp[m][n - 1] = dp[m - 1][n] = 1;

        //填表

        for(int i = m - 1; i >= 0; i--)

        {

            for(int j = n - 1; j >= 0; j--)

            {

                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];

                dp[i][j] = max(1,dp[i][j]);

            }

        }

        return dp[0][0];

    }

};

题后总结

通过今天的题，我们可以总结出以下几点

1.填表时需要使用原表上的数据时，行列各减1

2.初始化部分的目的：保证填表时不越界

                                  保证填表时后面的数据正确

3.如何正确初始化：结合状态表示和状态转移方程，进行分析哪些地方存在越界的可能性

那么本篇文章的内容就先到此结束，我们下期文章再见！！！

记得一键三联哦