【剑指offer第九天】动态规划(中等)

约定不等于承诺〃 2022-09-11 12:09 152阅读 0赞

#### 第一题 ####

连续最大子数组的和  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]  
动态规划，注意点：如果dp\[i-1\]即前边i-1的最大连续子串和为负数，那么结果就为nums\[i\]。保存并记录max值返回结果

class Solution { 
        public int maxSubArray(int[] nums) { 
            int l = nums.length;
            if(l == 0){ return 0;}
            int []dp = new int[l];
            dp[0] = nums[0];
            int max = dp[0];
            for(int i = 1;i < l;i++){ 
                dp[i] = Math.max((dp[i - 1] + nums[i]),nums[i]);
                max = Math.max(dp[i],max);
            }
            return max;
        }
    }

#### 第二题 ####

礼物的最大价值  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
初始化第一行和第一列的数值，然后使用动态规划，其余的数值和只能由上边一行或左边一列的某个数相加得到

class Solution { 
        public int maxValue(int[][] grid) { 
            int r = grid.length,c = grid[0].length;
            int [][]dp = new int[r][c];
            dp[0][0] = grid[0][0];
            for(int i = 1;i < r;i++){ 
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }
            for(int j = 1;j < c;j++){ 
                dp[0][j] = dp[0][j - 1] + grid[0][j];
            }
            for(int i = 1;i < r;i++){ 
                for(int j = 1;j < c;j++){ 
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }
            }
            return dp[r-1][c-1];
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ef3be064447748caae081ec4ff86bd1c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4758e1a3e8ea4bd28090a301bb4e090d.png