[剑指offer]面试题第[47]题[JAVA][礼物的最大价值][动态规划]

缺乏、安全感 2023-02-28 11:22 14阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1动态规划 ######

动态规划流程  
第 1 步：设计状态  
f(i, j)f(i,j) 为从棋盘左上角走至单元格 (i ,j)(i,j) 的礼物最大累计价值  
第 2 步：状态转移方程  
f(i,j)=max\[f(i,j−1),f(i−1,j)\]+grid(i,j)  
第 3 步：考虑初始化  
![在这里插入图片描述][20200721111640644.png]

第 4 步：考虑输出  
![在这里插入图片描述][20200721111650989.png]

第 5 步：考虑是否可以状态压缩  
![在这里插入图片描述][20200721111705384.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        public int maxValue(int[][] grid) { 
        //m 列数 n 行数
            int m = grid.length, n = grid[0].length;
            for(int j = 1; j < n; j++) // 初始化第一行
                grid[0][j] += grid[0][j - 1];
            for(int i = 1; i < m; i++) // 初始化第一列
                grid[i][0] += grid[i - 1][0];
            for(int i = 1; i < m; i++)
                for(int j = 1; j < n; j++) 
                    grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            return grid[m - 1][n - 1];
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2. 压缩空间可以在原数组上操作 行列 ######

###### 3.想清楚应该加什么，切忌想当然 ######

###### 3.类似题目[\[Leetcode\]\[第64题\]\[JAVA\]\[64. 最小路径和\]][Leetcode_64_JAVA_64.] ######

转载链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/solution/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/cfc01937b2ac4794aa20dcc7dd115f90.png
[20200721111640644.png]: https://img-blog.csdnimg.cn/20200721111640644.png
[20200721111650989.png]: https://img-blog.csdnimg.cn/20200721111650989.png
[20200721111705384.png]: https://img-blog.csdnimg.cn/20200721111705384.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020072111154348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[Leetcode_64_JAVA_64.]: https://leetcode-cn.com/problems/minimum-path-sum/