剑指 Offer 42. 连续子数组的最大和

题目链接

思路：1、dp[i]表示以i为结尾的连续子数组的最大和。

2、递推公式。dp[i]可以由两个方向推导来，一是延续之前的子数组继续累加，二是舍弃掉前面的子数组，从当前位置重新开始累加，这两种情况取最大值，dp[i]=max(dp[i-1]+nums[i],nums[i])

3、初始化dp数组。dp[0]是以0为结尾的最大子数组和，两个方向的结果都是nums[0]，非零下标都依次由之前的推导来，所以不用初始化

4、遍历顺序。由递推公式看出dp[i]是依赖于dp[i-1]的，所以遍历顺序就是从前往后遍历

5、打印dp数组

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        int result=dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);//一个是延续前面的子数组继续累加，一个是把前面抛弃掉，从新累加
            //由以上递推公式看出后一个都会由前一个推出来，所以非零下标不需要初始化
            if(dp[i]>result) result=dp[i];
        }
        return result;
    }
};

47. 礼物的最大价值

题目链接

本题没有看题解，直接自己写的，思考过程就是动规五部曲。本题和力扣62.不同路径比较像。

1、dp数组的含义。显然要用一个二维dp数组来记录信息。dp[i][j]表示到达i,j时可以拿到礼物的最大价值。

2、递推公式。题目中说的很明确了，每次只能向下向右，所以dp[i][j]只能由上面和左面推导来，dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])

3、初始化。dp[0][0]显然就只能是nums[0][0]，然后因为需要从上面和左边推导出来，所以第一行第一列都需要初始化，初始化的值是累加后的值。

4、遍历顺序。就是从上到下从左到右。

5、打印dp数组。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size(),0));
        dp[0][0]=grid[0][0];
        int sum=grid[0][0];
        for(int i=1;i<grid[0].size();i++){
            sum+=grid[0][i];
            dp[0][i]=sum;
        }
        sum=grid[0][0];
        for(int i=1;i<grid.size();i++){
            sum+=grid[i][0];
            dp[i][0]=sum;
        }
        for(int i=1;i<grid.size();i++){
            for(int j=1;j<grid[0].size();j++){
                dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

里面累加的过程还是需要再熟练，注意sum要定义在外面，不然每次遍历sum都会被重新赋值；初始化完第一行后需要将sum重新置为grid[0][0]，重新累加。

出错原因：dp数组初始化里面没有写vector<int>。