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

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

前言：

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

正文：

1.珠宝的最高价值

1.1.题目来源

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

1.2.题目解析

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

1.3.思路讲解

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

1.状态表示

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

2.状态转换方程

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