google网站推广,重庆建设信息,德宏北京网站建设,陕西建设网综合综合服务中心DP学习第五篇之礼物的最大价值
剑指 Offer 47. 礼物的最大价值 - 力扣#xff08;LeetCode#xff09; 一.题目解析 二. 算法原理
状态表示 tips: 经验题目要求。以[i,j]位置为结尾#xff0c;。。。
dp[i][j]: 到达[i, j]位置时#xff0c;此时的最大礼物价值
状态转移…DP学习第五篇之礼物的最大价值
剑指 Offer 47. 礼物的最大价值 - 力扣LeetCode 一.题目解析 二. 算法原理
状态表示 tips: 经验题目要求。以[i,j]位置为结尾。。。
dp[i][j]: 到达[i, j]位置时此时的最大礼物价值
状态转移方程 tips: 用之前或之后的状态推导出dp[i]的值。根据最近的一步来划分问题
到达[i, j]位置之前 从[i - 1, j]位置向下走一步到[i, j] 从[i, j - 1]位置向右走一步到[i, j] 即dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) g[i][j]
初始化 tips: 保证填表的时候不越界。增加虚拟节点
虚拟节点里面的值要保证后面填表是正确的 以起始位置为结尾则要保证第一个位置dp[1][1] g[1][1]。此时初始化时可以选择将虚拟节点的值都设置为0保证后续填表的正确性 下标的映射关系 dp表映射到原矩阵横纵坐标-1 填表顺序
从上往下填写每一行每一行从左往右
返回值
题目要求到达右下角的礼物价值
即return dp[m][n]
三. 编写代码
class Solution {
public:int maxValue(vectorvectorint g) {//1.创建dp表//2.初始化//3.填表//4.返回值int m g.size(), n g[0].size();vectorvectorint dp(m 1, vectorint(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]) g[i - 1][j - 1];return dp[m][n];}
};观看~~
