题目
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思考
1、一开始使用前缀和
2、后面看了评论，学习了一下动态规划 动态规划
代码和注释
class Solution {
// 这里使用动态规划的思想
public int maxSubArray(int[] nums) {
// 定义状态数组
int[] dp = new int[nums.length];
// 动态规划的初始状态
dp[0] = nums[0];
int max = dp[0];
// 由初始状态我们可以知道直接跳过第一个值
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}
}
总结
1、动态规划思考流程
2、上题步骤如下
- （1）设计状态=》连续数组相加
- （2）状态转移公式max(dp[i-1] + num[i]，num[i])=》以前面的为界的状态函数
- （3）设计状态数组dp
- （4）初始化状态是num【0】的值
- 注意：循环开始的地方一定要注意
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/96148.html
