动态规划|【路径问题】礼物的最大价值（LCR 166.珠宝的最高价值）

题目

LCR 166. 珠宝的最高价值

（现在leetcode上面是这个题）这个题跟下面这个题叙述方式一样，就拿下面这个 题来讲解）

题目描述：

在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例1：

输入：[[1,3,1],[1,5,1],[4,2,1]]

输出：12

解释：路径1-3-5-2-1可以拿到最多价值的礼物

题目解析

用示例1 来举例：输入[[1,3,1],[1,5,1],[4,2,1]]，形成如下的一个3*3的矩阵，我们把这个二维矩阵叫cost矩阵，每个位置都是一个对应价值的礼物，要求我们拿到最多价值的礼物，那就意味着，要走最大的值

题目中说从左上角出发，每次可以向下走或者向右走，那个数值大往哪走，右下角为终点，

思路

1.状态表示

       我们这里以某一个位置为结尾来确定状态表示，又根据题目要求，需要我们确定所走路径的拿到礼物的最大价值，所以状态表示dp[i][j]表示起点走到【i，j】位置，此时拿到礼物的最大价值。

2.状态转移方程

       状态表示的经验就是根据最近的一步划分问题，那我们怎么到达【i，j】，第一种要么从左边向右走到【i，j】位置，要么从上边向下走到【i，j】位置

所以dp[i][j]可以有两种方式得来

       a)从左边向右走：也就是从【i，j-1】位置走到【i，j】位置，然后拿到【i，j】位置的礼物价值，如果要起点到【i，j】位置拿到礼物的价值最大（dp[i][j])，就需要起点到【i，j-1】位置拿到礼物的价值最大(dp[i][j-1]),因此dp[i][j]=dp[i][j-1]+cost[i][j]。

       b)从上边向下走：同理a，这个方式对应的状态转移方程为dp[i][j]=dp[i-1][j]+cost[i][j]。

最后取这两种情况的最大值就行

3.初始化

之前说过，初始化的目的就是为了让填表不越界，我们 首先要分析填哪些位置回越界，因为填表的时候是根据状态转移方程来填表的，状态转移方程

根据这两个公式计算后用最大的那个值填表，计算是一个位置需要这个位置上面的那个值，和这个位置左边的值，但是第一行没有上面的值，第一列没有左边的值。所以第一行和 第一列需要初始化

之前也讲过，虚拟 结点的初始化，虚拟结点就是在创建dp表的时候多创建一行和多创建一列，然后从【1，1】位置开始填表。

虚拟结点里面的值要确保dp表中填的值的准确性。所以填0是最合适的，相当于里面礼物的的价值为0。

4.填表顺序

从上至下，从左至右

5.返回值

因为多开了一行和一列，所以返回dp[m][n]就行。

代码

int jewelleryValue(int** frame, int frameSize, int* frameColSize) 
{
    //创建dp表
    int dp[1000][1000]={0};
    //初始化这个刚好全是0就不用初始化了
    //行和列
    int m=frameSize;
    int n=frameColSize[0];
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++)
        {
            dp[i][j]=frame[i-1][j-1]+((dp[i-1][j]>dp[i][j-1])?dp[i-1][j]:dp[i][j-1]);
        }
    }
    return dp[m][n];
}

空间复杂度：O(mn)

时间复杂度：O(mn)