解锁动态规划的奥秘：从零到精通的创新思维解析（4）

解锁动态规划的奥秘：从零到精通的创新思维解析（4）

前言：

小编在前几天讲述了动态规划相关的题目，今天继续跟着上次的脚步，继续进行动态规划相关题目的讲解，下面我们一起走进动态规划的世界。

正文：

1.珠宝的最高价值

1.1.题目来源

和之前一样，本题同样来自于力扣，下面给出它的链接：LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

1.2.题目解析

本题目其实就是个pro版本的不同的路径问题，这个问题小编在之前的博客解答过，由于本文章写的时候那篇文章还没有发布，所以各位想看那个题目的可以进我主页来看一下：忘梓.-CSDN博客，下面进入正题，本题目是给定我们一个二维矩阵的珠宝价，并且每一个位置都有其价值，现在给定了我们几个规则，简单来说就是：我们从左上角开始拿珠宝，每次我们可以选择从右边或者下边走进行拿珠宝直到我们走到珠宝架子的右下角，问我们如何拿珠宝才可以拿到最高价值的珠宝，经过我这么一说，相信不少小伙伴都可以想到不同的路径那个题目，只不过此时这个题目与那个题目的不同就是本题是求解走到右下角时的珠宝的最高价值，题目的分析就到这里，下面我们进行本题目的思路讲解。

1.3.思路讲解

对于动态规划的题目，我们还是需要设置好一个dp表（并不是每一个动态规划就只有一个dp表，之后小编也会讲解多状态dp表的题目），此时我们自然的可以设置一个二维的dp表（题目分析得来），然后我们就正常五步走来对动态规划的题目进行求解。

1.状态表示

此时对于状态表示，我们依旧是按照经验+题目分析的角度来正确的表示出dp表，一般我们可以以某个位置为开头，或者以某个位置为结尾来进行状态的分析，通过对题目的解读，此时我们可以将其状态表示为以[i，j]位置为结尾时，从开头到[i，j]时的珠宝的最大价值，之后我们根据这个状态就可以书写状态转移方程了。

2.状态转换方程

此时我们根据题目给予我们的帮助，可以知道此时我们可以往右拿珠宝或者往下拿珠宝，当我们计算dp[i] [j]的时候，可以先计算上面的价值或者左边的价值，取他们中的最大值，然后加上自身，就可以计算出dp[i] [j]的值，此时我们可以如下图进行分析：

此时我们通过max函数计算其中的最大值即可，此时我们让最大值再加上当前位置本身的值即可。其代码如下所示：

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

3.初始化

本题和之前讲的路径问题一样，我们在初始化的时候都可以加上几个虚拟节点，来减小我们为了初始化的次数，因为此时如果我们不用虚拟节点的话，我们就要对第一行和第一列进行初始化的操作，有了虚拟结点以后，就可以大大减少我们的工作量了，此时我们可以根据状态转换方程来推算此时我们如何初始化，此时虚拟节点应该遵循以下两个原则：

1.虚拟节点的值要保证后面填表是正确的。

2.下标的映射

此时我们可以推算出此时的第一行和第一列的值为0即可，这样就可以确保此时的虚拟节点的值不影响我们之后填表时的值（不明白的读者朋友可以自行画个表看一下，其实大多数虚拟节点我们都是可以很快的知道它们的值的）。

4.填表顺序

此时我们通过方程可以知晓此时的填表顺序是从上到下，从左到右的。

5.返回值

因为此时我们求得的是到达最后一个位置时的珠宝的最高价值，所以我们返回最后一个位置的值即可，即dp[m] [n]。

1.4.代码讲解

此时我们需要先知道题目给定我们的行和列，通过vector容器给定我们的接口就可以知晓，之后我们要开辟一个dp表，此时dp表要多开一行一列，里面的值均为0即可。

int m = frame.size(),n = frame[0].size();
vector<vector<int>>dp(m + 1,vector<int>(n + 1));

之后我们就根据状态转换方程进行填充dp表即可，此时我们不用填第一行和第一列的dp表了，因为这样会让我们越界，虚拟节点本来就是为了不越界诞生的，这样做的话之间的努力就白费了。在填完表后，返回最后一个位置的数据即可。

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];

1.5.完整代码展示

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));
        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];
    }
};

2.下降路径的最小和

2.1.题目来源

和之前的题目一样，本题同样来自于力扣，下面小编给出该题目的链接：931. 下降路径最小和 - 力扣（LeetCode）

2.2.题目分析

本题目的分析也是比较容易的，此时我们通过读题目就可以知道本题的大致题意，这个题目简单来说，就是给定我们一个方形数组，此时我们需要从每一行选择一个数，选择下一个数的时候，当我们选择下一行的数据的时候，此时我们有三种选择方法，分别是：下左，正下方，下右方来进行选择，此时我们选择到最后一行的时候，其中把之前路径加起来的所有路径中的最小和，这就是本题目的题目分析，下面小编开始进行题目思路讲解。

2.3.思路讲解

对于动态规划的题目，我们应当还是需要先建立一个dp表，此时因为这个空间是二维的，所以我们需要构造一个二维的dp表，之后我们还是按照动态规划的分析的五步走就好。

1.状态表示

对于状态表示，无非就是经验 + 题目分析来进行作答（线性dp问题），此时我们可以以i位置为结尾或者开头进行状态表示，对于本题，小编的解法就是以i位置为结尾进行讨论，那么此时的dp[i] [i]应该表示为到达[i,j]时，此时的下降路径最小和，我们依据此时的状态表示，就可以书写出状态转换方程了。

2.状态转换方程

此时的方程我们可以根据题目的分析来进行求解，此时题目告诉我们往下走的方式有三种，所以对应着往上走的方法也是有三种的，分别是往上左来，正上方来，上右来，所以对应着的dp式子也有三种，因为要求最小下降路径和，所以我们应该求他们中的最小，然后加上当前位置的值即可，具体分析图可以看下图。

具体的代码如下：

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

3.初始化

初始化同样也是一个令人头疼的问题，当然这个题目的初始化也是容易看出来的，如果我们想要直接初始化那么就需要对第一行，第一列以及最后一列进行初始化，可以说非常的麻烦，所以为了避免麻烦，我们还是需要虚拟节点来解决这个问题，对于虚拟节点，我们需要遵循以下两个原则：

1.虚拟节点的值要保证后面填表是正确的。

2.下标的映射。（原数组和dp表之间的差异，此时让原数组行列-1就是dp表对应的位置）

本题的虚拟节点填值难度不大，此时我们需要保证第一行全部为0，因为我们在真正的第一行时需要用到虚拟的第一行的值，为了不影响结果，此时我们让其它位置的结点为最大值，避免对于他们的使用，这就是本题的初始化，等会在代码的时候更好看出来。

4.填表顺序

因为我们是以i位置为结尾的，所以我们需要前面的数据，所以从上往下，从左往右填。

5.返回值

此时我们不知道最后一行哪个位置的值最小，所以此时我们仍需循环去找到最后一行最小的数，找到后返回即可。

2.4.代码讲解

首先，我们仍需设置一个dp表，此时这个dp表要多开辟两列，多开辟一行，并且将里面的值先全部设置为int的最大值，之后我们再给特殊的第一行进行二次初始化。

int m = matrix.size(),n = matrix[0].size(); //前面表示行，后面表示列
vector<vector<int>> dp(m + 1,vector<int>(n + 2,INT_MAX));
for(int i = 0; i < n + 2 ; i++)
dp[0][i] = 0;  //让第一行为0

之后我们还是老老实实的按照状态转换方程填表即可，此时填表我们可以直接从第二行开始填，到最后一行结束，从第二列开始填，到倒数第二列结束，此时我们就完成了dp表的填写。

for(int i = 1 ; i <= m;i++)
    {
        for(int j = 1 ; j<= n ;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]; //min函数只可以比骄两个数，对于三个数可以嵌套处理
        }
    }

在所有数据填完后，我们仅需找到最后一行数据的最小值即可，摘到后返回即可（循环+最小值函数）。

int ret = INT_MAX;
for(int i = 1 ; i <= n ;i++)
ret = min(ret,dp[m][i]);
return ret;

2.5.完整代码展示

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size(),n = matrix[0].size(); //前面表示行，后面表示列
        vector<vector<int>> dp(m + 1,vector<int>(n + 2,INT_MAX));
        for(int i = 0; i < n + 2 ; i++)
        dp[0][i] = 0;  //让第一行为0
        for(int i = 1 ; i <= m;i++)
        {
            for(int j = 1 ; j<= n ;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]; //min函数只可以比骄两个数，对于三个数可以嵌套处理
            }
        }
        int ret = INT_MAX;
        for(int i = 1 ; i <= n ;i++)
        ret = min(ret,dp[m][i]);
        return ret;
    }
};

3.总结

截止到目前，本文的内容已经全部结束了，今天小编还是讲述了两个题目，希望各位读者好好的理解，如果有不懂的地方可以随时私信小编，小编会在空闲时间及时回复，最近我在实训，所以文章发布的有点慢，各位读者朋友见谅，不过当你看到这篇文章的时候，可能小编已经结束实训了，因为这是我的库存（理直气壮），一起学习的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！