剑指offer day9 动态规划(中等)
最后更新于
这有帮助吗?
最后更新于
这有帮助吗?
day9题目:、
知识点:数组、分治、动态规划,难度为简单、中等
学习计划链接:
简单
中等
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
注意:本题与主站 53 题相同:
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
提示:
0 < grid.length <= 200
0 < grid[0].length <= 200
dp[i][j]
代表i行j列能拿到礼物的最多价值
注意先初始化第一行和第一列
从上方或左方转移过来,状态转移方程为 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
、、
、、
在做过主站的题目,每次如果加上去之后会使当前和小于0,那么这个当前和只会让后面的变小所以直接舍弃,将nowsum重新置为0。
非常经典的走迷宫问题的换个说法,就有考到类似的。