首页 > 其他分享 >[leetcode]第 9 天 动态规划(中等)

[leetcode]第 9 天 动态规划(中等)

时间:2022-12-31 21:23:48浏览次数:42  
标签:pre nums int max 中等 grid 动态 leetcode dp

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

相关文章

  • leetcode-559. N 叉树的最大深度
    559.N叉树的最大深度-力扣(Leetcode)dfs/***DefinitionforaNode.*typeNodestruct{*Valint*Children[]*Node*}*/funcmaxDepth(roo......
  • SpringBoot动态更新yml文件
    前言在系统运行过程中,可能由于一些配置项的简单变动需要重新打包启停项目,这对于在运行中的项目会造成数据丢失,客户操作无响应等情况发生,针对这类情况对开发框架进行升级提......
  • Allure08-动态用例优先级与链接
    动态用例优先级allure.dynamic.severity(用例优先级)可以使用参数化的参数只能放到函数和方法中对于一个子功能或测试需求的每一条用例,都可以有自己的severity写法......
  • LeetCode第 94 场双周赛
    1.最多可以摧毁的敌人城堡数目题目最多可以摧毁的敌人城堡数目Solution可以第一重循环找到\(1\),然后从该位置分别向左和向又寻找\(-1\),寻找过程中遇到\(1\)则停止,不......
  • Allure06-动态测试集与功能特性
    动态测试集特性allure.dynamic.suite('某用例所属的测试集名称')动态特性放到函数或方法中不建议使用allure.dynamic.suite,否则会导致测试集名称显示混乱:既包含模块名......
  • Allure07-动态用例标题、用例描述和测试步骤
    动态用例标题allure.dynamic.title('动态用例标题')必须放在函数、方法之内可以使用参数化的参数每条用例执行一次会覆盖@allure.title动态用例描述allure.dy......
  • SpringBoot动态更新yml文件
    前言在系统运行过程中,可能由于一些配置项的简单变动需要重新打包启停项目,这对于在运行中的项目会造成数据丢失,客户操作无响应等情况发生,针对这类情况对开发框架进行升级提......
  • LeetCode周赛325
    到目标字符串的最短距离题目SolutionclassSolution{public:intclosetTarget(vector<string>&words,stringtarget,intstartIndex){intn=wo......
  • leetcode笔记——二分图
    785.判断二分图-力扣(LeetCode)二分图实际上就是这个图里所有的环都是偶数个边,一般采取染色法来做通过dfs判断每个节点与其邻居节点是否是同一种颜色,如果有的话,那就一定......
  • #yyds干货盘点# LeetCode程序员面试金典:三步问题
    1.简述:三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。示......