1.题目的特点：

• 计数

有多少种方式走到右下角；

有多少种方式选出K个数使得和是sum;

• 求最大最小值

从左上角走到右下角路径的最大数字和；

最长上升子序列长度；

• 求存在性

取石子游戏，先手是否必胜；

能不能选出K个数使得和为sum；

2.动态规划的4大组成部分

1.确定状态

在解动态规划的时候需要开辟一个数组，数组的每个元素f[i]或者f[i][j]具体代表着什么。

确定状态需要两步：

• 最后一步

我们不关心前面的K-1步是如何实现的，而且我们也不确定最后一步具体选什么，但是我们确定前面k-1步得到了想要的结果，而且前k-1步为最优的解法。

• 子问题

2.转移方程

比如：设状态f[x]=最少用多少枚硬币拼出X

对于任意X:

f[x]=min(f[x-2]+1,f[x-5]+1,f[x-7]+1)

3.初始条件和边界情况

初始条件：f[0]=0;

4.计算顺序

• 初始条件：f[0]=0;
• 然后计算f[1]，f[2]，....，f[27]
• 当我们计算f[x]时，f[x-2]，f[x-5]，f[x-7]都已经被计算。

一、字符串类

1.最长回文子串（leetcode 5）

• 题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

• 分析：

状态P(i, j)：以 i 开始 j 结尾的回文子串

状态转移方程：

表格：

class Solution {
public:
    string longestPalindrome(string s) {
        
        int m=s.length();
        //dp: 以i为起点j为终点的子串是否为回文
        vector<vector<bool>> dp(m,vector<bool>(m,false));
        for(int i=0;i<m;i++)
            dp[i][i]=true;

        //以列的填表
        int maxLength=1;
        int begin=0;
        for(int j=1;j<m;j++)
        {
            for(int i=0;i<j;i++)
            {
                //最外层元素不相等
                if(s[i]!=s[j])
                    dp[i][j]=false;
                //最外层元素相同
                else
                {
                    //子串的长度小于2
                    if(j-1-(i+1)+1<2)
                        dp[i][j]=true;
                    else
                        dp[i][j]=dp[i+1][j-1];
                }
                //最大长度
                if(j-i+1>maxLength&&dp[i][j])
                {
                    maxLength=j-i+1;
                    begin=i;
                }

            }
        }
        return s.substr(begin,maxLength);
    }
};

2.最长公共子序列（leetcode 1143）

• 题目描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
 

提示:

1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。

• 分析：

状态dp(i, j)：对于 s1[1..i] 和 s2[1..j],他们对应的最长公共子序列的长度为dp[i][j]

状态转移方程：

• 当s1[i]==s2[j],说明这两个字符是公共的字符，只要考察其子问题，dp[i−1][j−1]的长度即可，在此基础上+1

• 当s1[i]!=s2[j],说明这两个字符不是公共的字符，只要考察其两个子问题，dp[i−1][j],dp[i][j−1],取max

表格：（m+1）*（n+1）用0行、0列表示某一字符串为空串的情况 

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {

        int m=text1.length();
        int n=text2.length();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        //text1为空串时
        for(int i=0;i<=n;i++)
        {
            dp[0][i]=0;
        }
        //text2为空串时
        for(int j=0;j<=m;j++)
        {
            dp[j][0]=0;
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //如果当前text1[i]==text2[j]，那么在i-1,j-1的最长长度上+1；
                if(text1[i-1]==text2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                {
                    //如果不等，则有两种情况，取最长的
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

 

 

 

 

 

 

1.爬台阶（leetcode 70）

• 题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

分析：

 我们最终的要求是爬到第n阶台阶（以第n阶台阶结尾），为了爬上第n阶台阶，我们有两种方式：

1. 第一种是从第i-1阶台阶，然后再爬1阶台阶；
2. 第二种是从第i-2阶台阶，然后再爬2阶台阶。

那么状态是：dp[i]为爬上第i阶台阶的方法，则

1. 状态方程：dp[i]=dp[i-1]+dp[i--2]，
2. 初始状态：dp[0]=dp[1]=1;

• 递归实现：

class Solution {
public:
    int climb(int n)
    {
        if(n==0||n==1)
            return 1;
        return climb(n-1)+climb(n-2);
    }
    int climbStairs(int n) {
        return climb(n);
    }
};

• 动态规划实现：

class Solution {
public:
    int climbStairs(int n) {
        //初始条件：第0阶台阶和第1阶台阶，只有1种方法
        if(n==0||n==1)
            return 1;
        int dp[n+1];
        dp[0]=1;
        dp[1]=1;
        //对于第i阶台阶，可以从第i-2阶台阶然后再爬2阶台阶，或者从第i-1阶台阶然后再爬1阶台阶。
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n];

    }
};

2.打家劫舍（leetcode 198）

• 题目描述：【难度简单】

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

• 分析：

首先，要求偷窃到最高金额，相当使用动态规划。

1. 转移方程：dp[i]=max(dp[j]+nums[i],dp[i]) (0<=j<=i-2),因为不能相邻两家
2. 初始状态：dp[i]=nums[i]；dp[0]=nums[0];
3. 最高金额：max(dp[i])

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int dp[nums.size()];
        dp[0]=nums[0];
        int maxVal=dp[0];
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=nums[i];
            for(int j=i-2;j>=0;j--)
            {
                // cout<<"i: "<<i<<" dp[i]: "<<dp[i]<<" j:"<<j<<" dp[j]: "<<dp[j]<<std::endl;
                dp[i]=max(dp[j]+nums[i],dp[i]);        
            }
            maxVal=max(maxVal,dp[i]);
        }
        return maxVal;
    }
};

3.跳跃游戏(leetcode 55)

• 题目描述：

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置（求存在性）。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

• 分析：

这道题判断是否能够到达最后一个位置，可以用动态规划来解决。

• 确定状态：

1. 最后一步：第ｉ－ｊ个位置能否到达，并且这个位置+i-j位置的步数能够到达第ｉ个位置；

• 转移方程：dp[i]=(dp[j]&&nums[j]+j>=i);（只要有一个位置能跳到，并这个位置能跳到第i个位置，就成了）
• 初始状态：dp[0]=true;
• 计算顺序：dp[0]，dp[1]，dp[2],.....;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool dp[nums.size()];
        dp[0]=true;
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=false;
            for(int j=i-1;j>=0;j--)
            {
                if(dp[j]&&j+nums[j]>=i)
                {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[nums.size()-1];
    }
};

4.跳跃游戏II（leetcode 45）

• 题目描述：

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
         从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

• 分析：

根据上一道题我们知道其状态转移方程为：dp[i] = min(dp[i]，dp[j] + 1), if (j < i && j + nums[j] >= i)，其中dp[i]为跳到当前位置i的最少步数。

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int n=nums.size();
        int dp[n+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<n+1;i++)
        {
            dp[i]=INT_MAX;
            for(int j=i-1;j>=1;j--)
            {
                if(j+nums[j-1]>=i)
                {
                    dp[i]=min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n]==INT_MAX?-1:dp[n];

    }
};

 注意：这道题无法这样提交，有时间限制，这样写的时间复杂度为O（n^2）。

5.不同路径（leetcode 62）

• 题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

• 分析：

• 确定状态：

1. 最后一步：从左边（i，j-1）或上边（i-1，j）过来；
2. 子问题：从左上角有多少种方式走到格子dp(i，j)（以dp[i][j]结尾）;

• 状态转移方程：

• 初始条件：

1. dp[0][0]=1：起点有一种方法；
2. i=0：第一行，只能横着走（一种方法）；
3. j=0：第一列，只能竖着走（一种方法）；

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(!m||!n)
            return 0;
        int dp[m][n];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0||j==0)
                    dp[i][j]=1;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];

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

6.不同路径II（leetcode 63）

• 题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

• 分析

这道题和上一道题基本类似，只不过需要注意其有障碍的位置，因为无法到达有障碍的位置，所以只要0种方法。

状态转移方程和上题一样。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        long dp[obstacleGrid.size()][obstacleGrid[0].size()];
        if(obstacleGrid.empty())
            return 0;
        if(obstacleGrid[0].empty())
            return 0;
        for(int i=0;i<obstacleGrid.size();i++)
        {
            for(int j=0;j<obstacleGrid[0].size();j++)
            {
                //有障碍物
                if(obstacleGrid[i][j]==1)
                {
                    dp[i][j]=0;
                    continue;
                }
                //起点
                if(i==0&&j==0)
                {
                    dp[i][j]=1;
                    continue;
                }
                if(j>0&&i==0)
                {
                    dp[i][j]=dp[i][j-1];
                }
                else if(i>0&&j==0)
                {
                    dp[i][j]=dp[i-1][j];
                }
                else
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }               
            }
        }
        return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
    }
};

7.最大正方形（leetcode 221）

• 题目描述：

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

• 分析：

dp(i,j) 表示以 (i,j)为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 dp 中的每个元素值呢？对于每个位置 (i,j)(i, j)(i,j)，检查在矩阵中该位置的值：

1. 如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1 组成的正方形中；
2. 如果该位置的值是 1，则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

                                   dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()||matrix[0].empty())
            return 0;
        int rows=matrix.size();
        int cols=matrix[0].size();

        int dp[rows][cols];
        int maxVal=INT_MIN;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(i==0||j==0)
                    dp[i][j]=matrix[i][j]-'0';
                else if(matrix[i][j]=='0')
                    dp[i][j]=0;
                else 
                    dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
                // cout<<"dp["<<i<<"]["<<j<<"]: "<<dp[i][j]<<" ";
                if(dp[i][j]>maxVal)
                    maxVal=dp[i][j];
            }
            // cout<<endl;
        }
        return maxVal*maxVal;

    }
};

8.统计全为1的正方形子矩阵（leetcode 1277）

• 题目描述：

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

• 分析：

这道题和最大正方形类似，只不过当我们求出一个正方形时，如果边长大于1，那么就含有边长a个正方形。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.empty()||matrix[0].empty())
            return 0;
        int rows=matrix.size();
        int cols=matrix[0].size();
        int dp[rows][cols];
        int ans=0;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(i==0||j==0)
                    dp[i][j]=matrix[i][j];
                else if(matrix[i][j]==0)
                    dp[i][j]=0;
                else
                    dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
                // cout<<"dp["<<i<<"]["<<j<<"]: "<<dp[i][j]<<" ";
                ans+=dp[i][j];
            }
            // cout<<endl;
        }
        return ans;
    }
};

9.乘积最大的子数组（leetcode 152）

• 题目描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

• 分析：

很容易想到状态转移方程为：dp[i]=max(dp[i-1]*nums[i],nums[i])，但是当遇到这种情况，例如：[-2,3,-4]，dp[2]如果按照前面所述的状态转移推导为：3，但是子数组[*2,3,-4]相乘后的乘积更大（24），所以还需要改变下状态转移方程：

需要考虑当前的数为正还是负：

• 如果为正，那么最大值乘以当前值，仍然为最大。
• 如果为负，那么最大值乘以当前值，就不是最大了。

所以，我们还需要记录最小值，当nums[i]为负时，最小值乘以nums[i]变成了最大值。

• 如果nums[i]为正

1. dp[i][0] = min(nums[i], nums[i] * dp[i - 1][0]) if nums[i] >= 0

2. dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1]) if nums[i] >= 0

• 如果nums[i]为负

1. dp[i][0] = min(nums[i], nums[i] * dp[i - 1][1]) if nums[i] < 0

2. dp[i][1] = max(nums[i], nums[i] * dp[i - 1][0]) if nums[i] < 0

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

10.最大子序列和（leetcode 53）

• 题目描述：

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

• 分析：

1. dp[i]：表示为以i元素结束的最大连续子数组之和。
2. 状态转移方程：dp[i]=max(dp[i-1]+nums[i]，nums[i]);
3. 因为dp[i]只与前一个状态有关，因此可以改写为dp=max(dp+nums[i],nums[i])
4. 初始化状态：dp[0]=nums[0]

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

 11.按摩师（leetcode 面试题17.16）

• 日期：2020/3/24
• 题目描述：

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

• 分析：

这道题需要求总预约时间最长，另外每一天存在两种选择，要么选，要么不选，而且还不能连着选，因为按摩师要休息，所以：

• 总时间最长=max(第n天时长+前n-2天最长总时间，前n-1天最长总时间）
• 初始化条件：第0天：0，第1天：第一天的时长。
• 注意：不能连着选。

• 实现：

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

12.最长重复子数组（leetcode 718）

• 题目描述：

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

提示：

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

• 分析：

这道题开始没有理解到子数组和子序列的区别：子数组默认是连续的，子序列默认是不连续的，首先最长的公共子数组长度dp[i][j]，需要判断A[0:i-1]与B[0:j-1]是公共子数组，而且A[i]==B[j]。

因此采用动态规划进行求解，首先初始第一行和第一列，然后根据上面的条件依次递推状态方程。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty()||B.empty())
            return 0;
        int ans=0;
        int dp[A.size()][B.size()];
        for(int i=0;i<A.size();i++)
        {
            for(int j=0;j<B.size();j++)
            {
                //初始化
                if(i==0)
                {
                    if(A[i]!=B[j])
                        dp[i][j]=0;
                    else
                        dp[i][j]=1;
                }
                else if(j==0)
                {
                    if(A[i]!=B[j])
                        dp[i][j]=0;
                    else
                        dp[i][j]=1;
                }
                else
                {
                    //当前为公共元素
                    if(A[i]==B[j])
                    {
                        //判断A以i-1结尾，B以j-1结尾的是不是公共子数组
                        if(dp[i-1][j-1]>=1)
                        {
                            dp[i][j]=dp[i-1][j-1]+1;
                        }
                        //如果前面不是，则当前公共子数组长度设置为1        
                        else
                            dp[i][j]=1;
                    }
                    //当前元素不相等，长度为0
                    else
                        dp[i][j]=0;    
                }
                // cout<<"dp: "<<dp[i][j]<<" ";
                //更新当前的公共子数组的长度
                ans=max(ans,dp[i][j]);
            }
            // cout<<endl;
        }
        return ans;
    }
};

13.通配符匹配（leetcode 44）

• 题目描述：

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

• 分析：

 

14. 最佳买卖股票时机含冷冻期（leetcode 309）

• 题目描述：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

• 分析：

状态：第i天有三种选择：买入、卖出、冷冻期

1. sell[i]表示截至第i天，最后一个操作是卖时的最大收益；
2. buy[i]表示截至第i天，最后一个操作是买时的最大收益；
3. cool[i]表示截至第i天，最后一个操作是冷冻期时的最大收益；

转移方程：

• sell[i] = max(buy[i-1]+prices[i], sell[i-1]) (第一项表示第i天卖出，第二项表示第i天冷冻)

第i 天选择卖出，那么从  到 i-1 天买入的最大利润+当前卖出的价格（有了买入才能卖出），到 i-1 天卖出的最大利润  选择最大值

• buy[i] = max(cool[i-1]-prices[i], buy[i-1]) （第一项表示第i天买进，第二项表示第i天冷冻）

第i 天选择买入，那么从  到 i-1 天冷冻期的最大利润 - 当前买入的价格（买股票是要花钱的），到 i-1 天买入的最大利润 选择最大值（规则2：卖出了后为冷冻期，不能买入股票）

• cool[i] = max(sell[i-1], buy[i-1], cool[i-1])

初始状态：

1. sell[0]=0；
2. buy[0]=-prices[0]；
3. cool[0]=0；

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if (n==0)
            return 0;
        int sell[n];
        int buy[n];
        int cool[n];

        sell[0]=0;
        buy[0] = -prices[0];
        cool[0]=0;
        for(int i=1;i<n;i++)
        {
            sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
            buy[i]=max(buy[i-1],cool[i-1]-prices[i]);
            cool[i] = max(sell[i-1],cool[i-1]);
        }
        return sell[n-1];
    }
};