后无效性原则：当前啊状态只与上一个状态有关

0/1背包问题（组合问题求最优解）

一、问题描述：有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]，价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

二、解题思路：用动态规划的思路，阶段就是“物品的件数”，状态就是“背包剩下的容量”，那么很显然 $f[i ,v]$ 就设为从前 i 件物品中选择放入容量为 v 的背包最大的价值。那么有两种情况：

第i个物品大于背包容量，那么无法放入， $dp[i][j]=dp[i-1][j]$
第i个物品小于等于背包容量，可以放入，则比较两种情况即放入和不放入，如果不放入i，最大价值就和 i 无关，就是 dp[i-1][j] , 如果放入第 i 个物品，价值就是 $dp[i-1][j-w[i]]+val[i]$ ，我们只需取最大值即可,选择最优解 $dp[i][j]=max{ dp[i-1][j],dp[i-1][j-w[i]]+val[i]}$ 。

c++

if j<w[i]
    dp[i][j]=dp[i-1][j]
else
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+val[i])

三、优化
即对二维dp表优化
动态规划的一个原则：
后无效性原则：当前的状态只与上一个状态有关,即二维dp表中只与上一行的数据有关，所以只留一行即可，每次刷新这个一维数组的值

c++

1 2	if j>=w[i] dp[j]=max(dp[j],dp[j-w[i]]+val[i])

注意要从后往前推，也即是循环从j=m到j=1,因为从前往后会覆盖数据，从后往前就可以用上轮的数据了

数位成本和为目标值的最大数字
体积：cost[i]
价值：

位数最多
字典序最大

面试题 17.16. 按摩师
最开始写的代码：

c++

class Solution {
public:
    int massage(vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        vector<int>dp(nums.size(),0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i =2;i<nums.size();i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.size()-1];
    }
};

这种情况没有考虑到休息两天的，比如[2,1,1,2]
300. 最长上升组序列
转移方程 dp[i]=max(dp[i],dp[j]+1)if(nums[i]>nums[j])

python

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n =nums.size();
        if (n == 0) return 0;
        vector<int>dp(n,1);
        for(int i =1;i<n;i++)
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j])
                    dp[i]=max(dp[j]+1,dp[i]);
            }
        return *max_element(dp.begin(), dp.end());
    }
};

方法二：
维护一个

最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

c++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp=0,result=nums[0];
        for(int i=0;i<nums.size();i++){
              if(dp>0)
                dp=dp+nums[i];
              else
                dp=nums[i];
               result=max(result,dp);
                 
        }
        return result;
    }
};

2.最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

c++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty())return 0;
        int dp[grid.size()][grid[0].size()];
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++)
                {
                    if(i==0&&j==0)  dp[0][0]=grid[0][0];
                    else if(i==0)
                        dp[i][j]= dp[i][j-1]+grid[i][j];
                    else if(j==0)
                        dp[i][j]= dp[i-1][j]+grid[i][j];
                    else
                        dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

买卖股票的最佳时机
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

python

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int min_val = 0x3f3f3f; //无穷大
        for (int i = 0; i < prices.size(); i++) {
            min_val = min(min_val, prices[i]);
            res = max(res, prices[i] - min_val);
        }
        return res;
    }
};