42. 连续子数组的最大和
思路
状态定义:dp[i]表示以nums[i]结尾的连续子数组的最大和;
状态转移方程:
dp[i - 1] > 0,dp[i] = dp[i - 1] + nums[i];
dp[i - 1] <= 0,dp[i] = nums[i];
初始化:
dp[0] = nums[0];
输出max(dp);
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}
47. 礼物的最大价值
思路
可以想到i > m - 1,j > n - 1时会有越界问题,但是看了题解之后发现思路错了。因为动态规划要把大问题拆分成子问题,这种思路还是没拆分好。。
状态定义:设动态规划矩阵 dpdp ,dp(i,j)dp(i,j) 代表从棋盘的左上角开始,到达单元格 (i,j)(i,j) 时能拿到礼物的最大累计价值。
转移方程:
i = 0, j = 0 : dp(i, j) = grid(i, j)
i = 0, j ≠ 0 : dp(i, j) = grid(i, j) + dp(i, j - 1)
i ≠ 0, j = 0 : dp(i, j) = grid(i, j) + dp(i - 1, j)
i ≠ 0, j ≠ 0 : dp(i, j) = grid(i, j) + max[dp(i, j - 1), dp(i - 1, j)]
初始化:
dp[0][0] = grid[0][0];
输出dp[m - 1][n - 1];
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;
if(i == 0) grid[i][j] += grid[i][j - 1] ;
else if(j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];
}
}
标签:pre,nums,int,max,中等,grid,动态,leetcode,dp
From: https://www.cnblogs.com/vincy9501/p/17017102.html