动态规划

动态规划步骤

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划的解题步骤（动规五部曲）

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

1.基础题目

509. 斐波那契数

题目难度：简单用时： 5 分钟标记：完成

//509. 斐波那契数
//递归
class Solution {
public:
    int fib(int n) {
        int res;
        if (n == 0) return 0;
        if(n == 1 || n ==2) return 1;
        else return fib(n-1)+fib(n-2);
    }
};

//动态规划
class Solution {
public:
    int fib(int n) {
        if(n==0)return 0;
        vector<int> res;
        res.resize(n+1);
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= n; ++i) {
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }
};

70. 爬楼梯

题目难度：简单用时： 5 分钟标记：完成

//70. 爬楼梯
class Solution {
public:

    int climbStairs(int n) {

        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a[46] = {0};
        a[0]=0,a[1]=1,a[2]=2;

        for (int i = 3; i <= n; ++i) {
            a[i] = a[i-1] + a[i -2];
        }
        return a[n];

    }
};

746. 使用最小花费爬楼梯

题目难度：简单用时： 5 分钟标记：完成

//746. 使用最小花费爬楼梯
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> res(cost.size()+1,0);
        if (cost.size() == 1) return cost[0];
        if (cost.size() == 2) return min(cost[0],cost[1]);
        for (int i = 2; i <= cost.size(); ++i) {
            res[i] =min(res[i-1] + cost[i-1],res[i-2]+ cost[i-2]);
        }
        return res[cost.size()];
    }
};

62. 不同路径

题目难度：简单用时： 5 分钟标记：完成

//62. 不同路径
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> res(m,vector<int>(n,1));
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                res[i][j] = res[i][j-1] + res[i-1][j];
            }
        }
        return res[m-1][n-1];
    }
};

63. 不同路径 II

题目难度：简单用时： 12 分钟标记：完成

//63. 不同路径 II
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.back().back() == 1) return 0;
        //改变标识
        for (int i = 0; i < obstacleGrid.size(); ++i) {
            for (int j = 0; j < obstacleGrid[0].size(); ++j) {
                if (obstacleGrid[i][j]) obstacleGrid[i][j] = -1;
            }
        }
        //第一层
        int flag = 1;
        for (int i = 0; i < obstacleGrid.size(); ++i) {
            if (obstacleGrid[i][0] == -1) flag=0;
            else obstacleGrid[i][0] = flag;
        }
        flag = 1;
        for (int i = 0; i < obstacleGrid[0].size(); ++i) {
            if (obstacleGrid[0][i] == -1) flag=0;
            else obstacleGrid[0][i] = flag;
        }


        int m = obstacleGrid.size(),n =obstacleGrid[0].size();
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == -1) continue;
                else if (obstacleGrid[i-1][j] == -1 && obstacleGrid[i][j-1] == -1) obstacleGrid[i][j] = 0;
                else if (obstacleGrid[i][j-1] == -1) obstacleGrid[i][j] = obstacleGrid[i-1][j];
                else if (obstacleGrid[i-1][j] == -1) obstacleGrid[i][j] = obstacleGrid[i][j-1];
                else if (obstacleGrid[i-1][j] != -1 && obstacleGrid[i][j-1] != -1) 
                obstacleGrid[i][j] = obstacleGrid[i][j-1] + obstacleGrid[i-1][j];

            }
   

        return obstacleGrid[m-1][n-1];
    }
};

343. 整数拆分

题目难度：中等用时： 12 分钟标记：未完成

从1遍历j，然后有两种渠道得到dp[i].

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)

//343. 整数拆分
class Solution {
public:
    int num[59];
    int integerBreak(int n) {
        num[2] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j <= i /2; ++j) {
                num[i]  = max(max(num[i],j*(i-j)),j*num[i-j]);
            }
        }
        return num[n];

    }
};

96. 不同的二叉搜索树

题目难度：中等用时： 10 分钟标记：完成

class Solution {
public:
    int numTrees(int n) {
        int dp[20]={1};
        dp[1] = 1;
        //递推公式dp[i] += dp[i-j] * dp[j]
        for (int i = 2; i <=n ; ++i) {
            for (int j = 0; j < i ; ++j) {
                dp[i] +=  dp[j] * dp[i- j - 1] ;
            }
        }
        return dp[n];
    }
};

64. 最小路径和

题目难度：中等用时： 10 分钟标记：完成

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

542. 01 矩阵

题目难度：中等用时： 10 分钟标记：完成

class Solution {
    int findmin(vector<vector<int>>&dp, int i, int j)
    {
        int mins = dp[i][j];
        if(i > 0) mins = min(mins,dp[i - 1][j]+1);
        if(j > 0) mins = min(mins,dp[i][j - 1]+1);
        if(i < dp.size() - 1) mins = min(mins,dp[i + 1][j]+1);
        if(j < dp[0].size() - 1) mins = min(mins,dp[i][j + 1]+1);
        return mins;
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        //初始化
        vector<vector<int>> dp(mat);
        for (int i = 0; i < mat.size(); i++)
            for (int j = 0; j < mat[0].size(); j++)
                if(mat[i][j] == 1) dp[i][j] = INT32_MAX / 2;

        //上边遍历
        for (int i = 0; i < mat.size(); i++)
            for (int j = 0; j < mat[0].size(); j++)
                dp[i][j] = findmin(dp,i,j);

        //下表遍历
        for (int i = mat.size() - 1; i >= 0; i--)
            for (int j =mat[i].size() - 1; j >= 0; j--)
                dp[i][j] = findmin(dp,i,j);

        return dp;
    }
};

221. 最大正方形（未完成）

题目难度：中等用时： 10 分钟标记：未完成

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxs = 0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                dp[i][j] = matrix[i][j] - '0';
                maxs = max(maxs,dp[i][j]);
            }
        }
    
        for (int i = 1; i < dp.size(); ++i) {
            for (int j = 1; j < dp[0].size(); ++j) {
                if (dp[i-1][j-1] >= 1 && dp[i][j] == 1)
                {
                    int flag = true , count = 1;
                    while (count <= sqrt(dp[i-1][j-1]))
                    {
                        if (!dp[i-count][j]||!dp[i][j-count])break;
                        count++;
                    }
                    dp[i][j] = count*count;
                }
                maxs = max(maxs,dp[i][j]);
            }
        }
        return maxs;
    }
};

//方法二
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxs = 0;
        vector<vector<int>> dp(matrix.size()+1,vector<int>(matrix[0].size()+1,0));
        for (int i = 1; i <= matrix.size(); ++i) {
            for (int j = 1; j <= matrix[0].size(); ++j) {
                if (matrix[i-1][j-1]=='1')dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
                maxs = max(maxs,dp[i][j]);
            }
        }
        return maxs * maxs;
    }
};

91. 解码方法

题目难度：中等用时： 10 分钟标记：完成

class Solution {
public:
    int numDecodings(string s) {
        vector<int> dp(s.size() + 1);
        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1;
        if (!dp[1]) return 0;

        //其他情况
        for (int i = 1; i < s.size(); ++i) {
            //情况一 如果前一个为1或者2
            if(s[i] == '0' && (s[i- 1] == '0' || s[i- 1] > '2')) return 0;
            if( (s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6') && s[i] > '0') dp[i+1] = dp[i] + dp[i - 1];
            else if(s[i] == '0') dp[i+1] = dp[i - 1];
            else dp[i + 1] = dp[i];
        }
        return dp.back();
    }
};

650. 只有两个键的键盘（未完成）

题目难度：中等用时： 10 分钟标记：完成

//方法一动态规划
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1,0);
        for (int i = 2; i <=n; ++i) {
            dp[i] = i;
            for (int j = 2; j <= (int)sqrt(n); ++j) {
                if (i % j == 0)
                {
                    dp[i] = dp[j] + dp[i / j];
                    break;
                }
            }
        }
        return dp[n];
    }
};

//方法二 求最大公因数和
class Solution {
public:
    int minSteps(int n) {
        if (n == 1) return 0;
        int i = sqrt(n);
        while (i > 1)
        {
            if (n % i == 0) return minSteps(i) + minSteps(n / i);
            i--;
        }
        return n;
    }
};

2.背包问题

1.0-1背包

问题描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

一维dp数组（滚动数组）

动规五部曲分析如下：

1.确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.一维dp数组的递推公式

dp[j]为容量为j的背包所背的最大价值，dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j] 相当于二维dp数组中的

dp[i-1][j]

，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

所以递归公式为：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3.一维dp数组初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。

4.一维dp数组遍历顺序(先物品，再背包，背包倒序)

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

完整代码：

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

416. 分割等和子集

题目难度：中等用时： 10 分钟标记：完成

题解：分为等和子集，可以理解为把集合划分为两份。让两份和相等。那么和的二分之一为背包容量，nums为物品，物品的价值等于物品的重量，求价值最大化。就是一个01背包问题，求最大背包能不能填满，即填满后等不等于nums的二分之一。

//416. 分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if (sum % 2 == 1) return false;
        else sum/=2;
        vector<int>dp(sum+1,0);

        for (int i = 0; i < nums.size(); ++i) {
            for (int j = sum; j >=nums[i]  ; --j) {
                dp[j] = max(dp[j],dp[j - nums[i]]+nums[i]);
            }
        }

        return dp.back() == sum;
    }
};

1049. 最后一块石头的重量 II

题目难度：中等用时： 10 分钟标记：未完成

那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。

在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

//1049. 最后一块石头的重量 II
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(),stones.end(),0) / 2;
        vector<int> dp(sum+1,0);
        for (int i = 0; i < stones.size(); ++i) {
            for (int j = sum; j >= stones[i]; --j) {
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return accumulate(stones.begin(),stones.end(),0)  - 2 * dp.back();
    }
};

494. 目标和

题目难度：中等用时： 10 分钟标记：未完成

//494. 目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if ((accumulate(nums.begin(),nums.end(),0) - target) % 2 == 1) return 0;
        if ((accumulate(nums.begin(),nums.end(),0) - target < 0))return 0;
        int ta = (accumulate(nums.begin(),nums.end(),0) - target) / 2;

        vector<int> dp;
        dp.resize(ta+1);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = ta; j >= nums[i]; --j) {
            dp[j]+=dp[j - nums[i]];
            }
        }
        return dp[ta];
    }
};

474. 一和零

题目难度：中等用时： 24 分钟标记：未完成

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //dp[i][j]为 i 个0 ，j个0时候，能最多的子集
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        //dp[i][j] = max(dp[i][j],dp[i - ze][j-one] + 1);
        for (int i = 0; i < strs.size(); ++i) {
            int ze = std::count(strs[i].begin(), strs[i].end(),'0');
            int one = strs[i].size() - ze;
            for (int j = m; j >=  ze; --j) {
                for (int k = n; k >= one; --k) {
                    dp[j][k] = max( dp[j][k],dp[j - ze][k-one] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

2.完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

每件商品都有无限个！

问背包能背的物品最大价值是多少？

首先在回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

518. 零钱兑换 II（组合）

题目难度：中等用时： 8 分钟标记：完成

//518. 零钱兑换 II
class Solution {
public:
    int change(int amount, vector<int>& coins) {

        vector<int> dp(amount+1,0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ（排列）

题目难度：中等用时： 6 分钟标记：未完成

//377. 组合总和 Ⅳ
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {

        vector<int> dp(target+1,0);
        dp[0] = 1;

        for (int i = 0; i <= target ; ++i)
         {
             for (int j = 0; j < nums.size(); ++j){
                 if (i-nums[j]>=0 && dp[i] < INT_MAX - dp[i-nums[j]])
                dp[i]+=dp[i-nums[j]];
            }
        }

        return dp[target];
    }
};

322. 零钱兑换

题目难度：中等用时： 6 分钟标记：完成

//322. 零钱兑换
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j <= amount ; ++j) {
                if (dp[j-coins[i]]!=INT_MAX)
                {
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount]==INT_MAX) return -1;
        return dp[amount];
    }
};

279. 完全平方数

题目难度：中等用时： 12 分钟标记：完成

//279. 完全平方数
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i) {
            for (int j = 1; j*j <= i ; ++j) {
                dp[i] = min(dp[i-j*j]+1,dp[i]);
            }
        }
        return dp[n];

    }
};

139. 单词拆分

题目难度：中等用时： 20 分钟标记：未完成

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < wordDict.size(); ++j) {
                if (i >= wordDict[j].size() && dp[i - wordDict[j].size()] && wordDict[j] == s.substr(i-wordDict[j].size(),wordDict[j].size()))
                {
                    dp[i] = true;
                }
            }
        }
        return dp.back();
    }
};

1155. 掷骰子等于目标和的方法数

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        //背包问题的动态规划
        //1155. 掷骰子等于目标和的方法数
        if(target < n || target > n * k) return 0;
        if(n == 1) return 1;
        const int M = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(target + 1));

        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= target; j++)
            {
                for (int m = 1; m <= k; m++)
                {
                    if(j >= m) dp[i][j]= (long)(dp[i][j] + dp[i - 1][j - m]) % M;
                }
                
            }
            
        }
        return dp.back().back();   
    }
};

3.总结

背包递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

动态规划：474.一和零(opens new window)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

遍历顺序

01背包

一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

完全背包

说完01背包，再看看完全背包。

先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

3.打家劫舍

198. 打家劫舍

题目难度：中等用时： 5 分钟标记：完成

//状态转移方程 当前最大值取决于前一个偷不偷 dp[i]为最大值
//dp[i] = max(dp[i-1],dp[i-2] + nums[i])
class Solution {
public:
    int rob(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-1],dp[i-2] + nums[i]);
        }
        return dp.back();
    }
};

213. 打家劫舍 II

题目难度：中等用时： 5 分钟标记：完成

//213. 打家劫舍 II
//和I 一样 去掉前后两个元素分别比较
class Solution {
public:
    int rob(vector<int>& nums)
    {
        if(nums.size() == 1)return nums[0];
        vector<int> s(nums.begin()+1,nums.end());
        vector<int> s2(nums.begin(),nums.end()-1);
        return max(getmax(s),getmax(s2));
    }
    int getmax(vector<int>& nums) {
        if(nums.size() == 1)return nums[0];
        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-1],nums[i] + dp[i-2]);
        }

        return dp[nums.size()-1];
    }
};

337. 打家劫舍 III

题目难度：中等用时： 15 分钟标记：未完成

动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。这道题目算是树形dp的入门题目（注意用后序遍历的方式推导）

class Solution {
    // 树返回一个列表，分别表示偷或者不偷此节点的最大值
    vector<int> robmax(TreeNode* root)
    {
        if (root == NULL) return {0,0};
        vector<int> left = robmax(root->left);
        vector<int> right = robmax(root->right);
        //偷cur，不能偷左右
        int tou = root->val + left[1] + right[1];
        //不偷cur，取左右最大
        int bu = max(left[0],left[1])+ max(right[1],right[0]);
        return {tou,bu};
    }
public:
    int rob(TreeNode* root) {
        vector<int> res =robmax( root);
        return max(res[0], res[1]);
    }
};

4.买股票

121. 买卖股票的最佳时机

题目难度：简单用时： 10 分钟标记：未完成

1.确定状态dp【i】【0】为第i天持有股票，包括买入。dp【i】【1】为没有股票，包括没买和卖出

2.初始化{-prices[0],0}

3.状态转移，dp【i】【0】 = 前一天持有股票和今天买入股票的最大值。dp【i】【1】 = 前一天不买股票和今天卖出股票的最大值

4.最后一定是dp【i】【1】不持有股票的状态

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][0] 持有 dp[i][1] 不持有
        vector<vector<int>> dp(prices.size(),{0,0});
        //持有包括一直持有和刚刚买入 ， 不持有包括卖出和不持有
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i-1][0],-prices[i]);
            dp[i][1] =  max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp.back()[1];
    }
};

122. 买卖股票的最佳时机 II

题目难度：中等用时： 10 分钟标记：完成

1.确定状态dp【i】【0】为第i天持有股票，包括买入。dp【i】【1】为没有股票，包括没买和卖出

2.初始化{-prices[0],0}

3.状态转移，dp【i】【0】 = 前一天持有股票和今天买入股票的最大值。dp【i】【1】 = 前一天不买股票和今天卖出股票的最大值

4.最后一定是dp【i】【1】不持有股票的状态

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

123. 买卖股票的最佳时机 III

题目难度：困难用时： 10 分钟标记：完成

1.确定状态dp【i】【0】为第一次第i天持有股票，包括买入。dp【i】【1】为第一次没有股票，包括没买和卖出，dp【i】【2】为第二次持有股票，dp【i】【3】为第二次没有股票。

2.初始化{-prices[0],0，-prices[0]，0}

3.状态转移，dp【i】【0】 = 第一次前一天持有股票和今天买入股票的最大值。dp【i】【1】 = 第一次前一天不买股票和今天卖出股票的最大值，dp【i】【2】 = 第二次前一天持有股票和今天买入股票的最大值。dp【i】【3】 = 第二次前一天不买股票和今天卖出股票的最大值

4.最后一定是dp【i】【3】第二次不持有股票的状态

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;
        vector<vector<int>> dp(prices.size() , {0,0,0,0});
        dp[0][0] = -prices[0];//第一次持有
        dp[0][2] = -prices[0];//第二次持有
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0] ,  - prices[i]);//第一次持有
            dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);//第一次不持有
            dp[i][2] = max(dp[i - 1][2] , dp[i - 1][1] - prices[i]);//第二次持有
            dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2] + prices[i]);//第二次不持有
        }
        return dp.back()[3];
    }
};

188. 买卖股票的最佳时机 IV

题目难度：困难用时： 10 分钟标记：完成

同上，就增加了循环

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() < 2) return 0;
        //初始化dp
        vector<vector<int>> dp(prices.size() , vector<int>(2 * k , 0));
        //初始化 第i次持有股票 为-prices[0]
        for (int i = 0; i < k; ++i) {
            dp[0][i * 2] = -prices[0];
        }

        for (int i = 1; i < prices.size(); ++i) {
            //第一次持有/不持有
            dp[i][0] = max(dp[i - 1][0] ,  - prices[i]);
            dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);
            //第 2 - k次持有/不持有
            for (int j = 1; j < k; ++j) {
                dp[i][2 * j] = max(dp[i - 1][2 * j],dp[i - 1][2 * j - 1] - prices[i]);
                dp[i][2 * j + 1] = max(dp[i - 1][2 * j + 1] , dp[i - 1][2 * j] + prices[i]);
            }
        }
        return dp.back()[2 * k - 1];
    }
};

309. 最佳买卖股票时机含冷冻期

题目难度：中等用时： 10 分钟标记：未完成

四个状态 -- 0：持有 1：卖出 2：冷冻期 3：不持有可以买入

需要注意的是到0 有3种方式-----0保持，2到0 ，3到0，到1只有一种方式0-1，到2一种方式1-2 ，到三两种方式保持和 2-3

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;
        vector<vector<int>> dp(prices.size() , {0,0,0,0});
        dp[0][0] = -prices[0];//第一次持有

        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0] , max(dp[i - 1][3] - prices[i],dp[i - 1 ][2] - prices[i]));//持有
            dp[i][1] = dp[i - 1][0] + prices[i];//卖出
            dp[i][2] = dp[i - 1][1];//冷冻期
            dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2]);//不持有- 可以买入的状态
        }
        return max(dp.back()[3], max(dp.back()[2],dp.back()[1]));
    }
};

714. 买卖股票的最佳时机含手续费

题目难度：中等用时： 10 分钟标记：完成

在买入的时候减去手续费

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

5.子序列问题

300. 最长递增子序列

题目难度：中等用时： 10 分钟标记：完成

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

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

674. 最长连续递增序列

题目难度：简单用时： 10 分钟标记：完成

//1.贪心解
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int maxs = 1;
        int res = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) maxs++;
            else maxs = 1;
            res = max(res,maxs);
        }
        return res;
    }
};

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

718. 最长重复子数组

题目难度：中等用时： 10 分钟标记：完成

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp【i】【j】。（特别注意： “以下标i - 1为结尾的A” 标明一定是以A[i-1]为结尾的字符串）。因为要求连续，所以要以dp【i】【j】结尾。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int maxs = 0;
        vector<vector<int>>dp(nums1.size() + 1,vector<int>(nums2.size() + 1,0));
        for (int i = 1; i <= nums1.size(); ++i) {
            for (int j = 1; j <= nums2.size(); ++j) {
                if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                maxs = max(maxs,dp[i][j]);
            }
        }
        return maxs;
    }
};

1143. 最长公共子序列

题目难度：中等用时： 10 分钟标记：完成

同上，因为不要求连续，所以不相等的时候dp【i】【j】要求其i -1 与j -1中最大值。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>>dp(text1.size() + 1,vector<int>(text2.size() + 1,0));
        for (int i = 1; i <= text1.size(); ++i) {
            for (int j = 1; j <= text2.size(); ++j) {
                if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp.back().back();
    }
};

1035. 不相交的线

题目难度：中等用时： 10 分钟标记：完成

这道题看似复杂，其实就是求最长公共递增子序列，与上一题相似。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>>dp(nums1.size() + 1,vector<int>(nums2.size() + 1,0));
        for (int i = 1; i <= nums1.size(); ++i) {
            for (int j = 1; j <= nums2.size(); ++j) {
                if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp.back().back();
    }
};

53. 最大子数组和

题目难度：中等用时： 10 分钟标记：完成

//1.贪心法
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int maxs = INT_MIN;
        int cur = 0;
        for (int i = 0; i < nums.size(); ++i) {
            cur+=nums[i];
            maxs = max(maxs,cur);
            if (cur < 0) cur = 0;
        }
        return maxs;
    }
};

//2.dp 公式---前一个和dp【i - 1】 + num【i】 与 num【i】的最大值
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxs = nums[0];
        vector<int>dp(nums.size() , 0);
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i-1] + nums[i],nums[i]);
            maxs = max(maxs,dp[i]);
        }
        return maxs;
    }
};

673.最长递增子序列的个数

题目难度：中等用时： 20分钟标记：未完成

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(),1);         //记录为以num[i]结束的最长子序列长度
        vector<int> count(nums.size(),1);      //记录为以num[i]结束的最长子序列长度个数
        int maccount = 1;
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i])
                {
                    if (dp[j] + 1 > dp[i]) //需要更新dp[i]，以及以j结束的count
                    {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                    else if (dp[j] + 1 == dp[i])//以j结束的最长字符串长度等于i count需要加j
                    {
                        count[i] += count[j];
                    }
                }
                maccount = max(dp[i],maccount);
            }
            
        }
        //寻找最长的长度
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (dp[i] == maccount) res+=count[i];
        }
        return res;
    }
};

413. 等差数列划分（未完成）

题目难度：中等用时： 10分钟标记：未完成

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if (nums.size() < 3) return 0;
        vector<int> dp(nums.size(),0);
        for (int i = 2; i < nums.size(); ++i) {
            if (nums[i] - nums[i-1] == nums[i-1] -nums[i-2]) dp[i] = dp[i-1]+1;
        }
        return std::accumulate(dp.begin(), dp.end(),0);
    }
};

6.编辑距离问题

392. 判断子序列

题目难度：中等用时： 10 分钟标记：完成

dp方法：记录相同个数，相同则dp等于上一个+1，不同则看j的上一个

//1.双指针法
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int slow = 0,fast = 0;
        while (fast < t.size() && slow < s.size())
        {
            if (s[slow] == t[fast]) slow++;
            fast++;
        }
        if (s.size() == slow) return true;
        return false;
    }
};
//2.dp法
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if (dp[s.size()][t.size()] == s.size()) return true;
        return false;
    }
};

115. 不同的子序列

题目难度：中等用时： 10 分钟标记：未完成

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>>dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
        for (int i = 0; i <= t.size(); ++i) dp[0][i] = 0;
        for (int i = 0; i <= s.size(); ++i) dp[i][0] = 1;
        for (int i = 1; i <=s.size() ; ++i) {
            for (int j = 1; j <= t.size() ; ++j) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
                else dp[i][j] = dp[i-1][j];
            }
        }

        return dp.back().back();
    }
};

583. 两个字符串的删除操作

题目难度：中等用时： 10 分钟标记：未完成

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for (int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
        for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
        for (int i = 1; i <=word1.size() ; ++i) {
            for (int j = 1; j <= word2.size() ; ++j) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i][j-1]+1, min(dp[i-1][j]+1,dp[i-1][j-1]+2));
            }
        }

        return dp.back().back();
    }
};

72. 编辑距离

题目难度：困难用时： 10 分钟标记：未完成

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for (int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
        for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
        for (int i = 1; i <=word1.size() ; ++i) {
            for (int j = 1; j <= word2.size() ; ++j) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i][j-1], min(dp[i-1][j],dp[i-1][j-1]))+1;
            }
        }

        return dp.back().back();
    }
};

10. 正则表达式匹配（未完成）

题目难度：困难用时： 10 分钟标记：未完成

class Solution {
public:
    bool isMatch(string s, string p) {
        // dp[i][j] 表示 s以i - 1结束，p以j - 1结束是否能匹配 （0 - n）
        vector<vector<bool>> dp(s.size() + 1,vector<bool>(p.size()+1, false));
        //初始化 dp[0][i] , s字符串为空时，p的*个数
        dp[0][0] = true;
        for (int i = 1; i <= p.size(); ++i) {
            if (p[i - 1] == '*')dp[0][i] =  dp[0][i-2];
        }

        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 1; j <= p.size() ; ++j) {
                //1.遇到 .
                if (p[j - 1] == '.') dp[i][j] = dp[i-1][j-1];
                //2.遇到两者相等
                else if(p[j - 1] != '*') dp[i][j] = dp[i-1][j-1] && p[j - 1] == s[i - 1];
                //3.遇到 p[i - 2] 和s[i-2]不匹配
                else if(p[j - 2] != '.' && p[j - 2] != s[i - 1])dp[i][j] = dp[i][j-2];
                //其他 ，遇到*
                else dp[i][j] = dp[i-1][j]||dp[i][j-1]||dp[i][j-2];
            }
        }
        return dp.back().back();
    }
};

7.回文问题

647. 回文子串

题目难度：中等用时： 10 分钟标记：未完成

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        int count = 0;
        for (int i = 0; i < s.size(); ++i) dp[i][i] = true;
        for (int i = s.size() -1 ; i >= 0; --i) {
            for (int j = i; j < s.size(); ++j) {
                if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1]))
                {
                    count++;
                    dp[i][j] = true;
                }
            }
        }
        return count;
    }
};

516. 最长回文子序列

题目难度：中等用时： 10 分钟标记：未完成

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

5. 最长回文子串

题目难度：中等用时： 10 分钟标记：完成

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));
        int maxstart,malen=0;
        for (int i = s.size()-1; i >=0 ; --i) {
            for (int j = i; j < s.size(); ++j) {
                if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1]))  dp[i][j] = true;
                if (dp[i][j] && malen < j - i +1)
                {
                    malen = j - i +1;
                    maxstart = i;
                }
            }
        }
        return s.substr(maxstart,malen);
    }
};

132. 分割回文串 II

题目难度：困难用时： 20分钟标记：未完成

class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>>dp(s.size(),vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0 ; --i) {
            for (int j = i; j < s.size(); ++j) {
                if (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1]))dp[i][j] = true;
            }
        }
        vector<int> res(s.size());
        for (int i = 0; i < s.size(); ++i) res[i] = i;

        for (int i = 1; i < s.size(); ++i) {
            if (dp[0][i])
            {
                res[i] = 0;
                continue;
            } else
            {
                for (int j = 0; j < i; ++j) {
                    if (dp[j+1][i]) res[i] = min(res[i],res[j]+1);
                }
            }
        }
        return res.back();
    }
};

动态规划

动态规划步骤​

动态规划的解题步骤（动规五部曲）​

1.基础题目​

221. 最大正方形（未完成）​

650. 只有两个键的键盘（未完成）​

2.背包问题​

1.0-1背包​

2.完全背包问题​

518. 零钱兑换 II（组合）​

377. 组合总和 Ⅳ（排列）​

3.总结​

背包递推公式​

遍历顺序​

01背包​

完全背包​

3.打家劫舍​

4.买股票​

5.子序列问题​

413. 等差数列划分（未完成）​

6.编辑距离问题​

10. 正则表达式匹配（未完成）​

7.回文问题​

动态规划步骤

动态规划的解题步骤（动规五部曲）

1.基础题目

221. 最大正方形（未完成）

650. 只有两个键的键盘（未完成）

2.背包问题

1.0-1背包

2.完全背包问题

518. 零钱兑换 II（组合）

377. 组合总和 Ⅳ（排列）

3.总结

背包递推公式

遍历顺序

01背包

完全背包

3.打家劫舍

4.买股票

5.子序列问题

413. 等差数列划分（未完成）

6.编辑距离问题

10. 正则表达式匹配（未完成）

7.回文问题