本文记录作者牛客刷题过程中与动态规划相关的题目。

一、爬楼梯类型

1、斐波那契数列

BM62 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(1) = 1, F(2) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

输入：n = 2
输出：1

点评

class Solution {
public:
    int Fibonacci(int n) {
        vector<int> dp(n+1,0);
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;++i){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

2、爬楼梯问题

BM63 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1 \leq n \leq 401≤n≤40

要求：时间复杂度：O(n)，空间复杂度： O(1)O(1)

输入：2
返回值：2
说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2  

点评

class Solution {
public:
    int jumpFloor(int number) {
        vector<int> dp(number+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=number;++i){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }
};

BM64 最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

整理后的代码如下：

int minCostClimbingStairs(vector<int>& cost) {
    int n=cost.size();
    vector<int> dp(n+1);
    dp[0]=cost[0];
    dp[1]=cost[1];
    for(int i=2;i<=n;++i){
        if(i==n){
            dp[i]=min(dp[i-1],dp[i-2]);
        }
        else{
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
    }
    return dp[n];
}

BM69 把数字翻译成字符串

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。

我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。

由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 ‘a’ 也可以看做是一个 ‘k’ 。但 10 只可能是 ‘j’ ，因为 0 不能编译成任何结果。

现在给一串数字，返回有多少种可能的译码结果

输入: "12"
输出: 2
解释: 2种可能的译码结果（”ab” 或”l”）  

点评

class Solution {
public:
    /* 解析：这道题定义0-25的数都可以翻译成对应的英文字母，给定一个多位数字，问有多少种方案
    存在多种翻译方案的原因在于，每次翻译可以只翻译1个数位，也可以一次性翻译2个数位，例如：
    16可以看做1和6分别进行翻译，也可以看做16一次性翻译
    这道题可以看做是抽象的爬楼梯问题：给定一个n位数，就是给了n个台阶
    每此只能翻译一个数或两个数就是，n个台阶里每此只能上一级或两级
    唯一的区别是爬两级需要做一个是否小于26的判断。
    【状态定义】：dp[i] 表示的含义为翻译前i个数字的方案数目
    【转移方程】：翻译前i位数只能是
    （1）第i位数字 无法和前面的数组合，比如 1245, 5 只能单独翻译，那么方法数和 124 是一样的
    dp[i]=dp[i-1]，[i-2,i-1]组成的数<10||>25
    （2）第i位数字 可以和前面的数组合，比如 1215, 5 可以选择 组合 和 不组合，最终结果为两种情况相加
    a. 选择组合，15看成是整体，那么 dp[i] = dp[i - 2]
    b. 不选择组合，5单独翻译，那么 dp[i] = dp[i - 1]
    最终结果：
    dp[i]=dp[i-1]+dp[i−2]，10<=[i-2,i-1]组成的数<=25
    */
    int translateNum(int num) {
        string numStr=to_string(num);
        vector<int> dp={0,0};
        dp[0]=1;
        dp[1]=1;
        // 循环[2,len]，因为dp[i]是定义前i位数字，最后求前len位数字
        for(int i=2;i<=numStr.length();i++){
            int temp=0;
            int digit=(numStr[i-2]-'0')*10+numStr[i-1]-'0';
            if(digit>=10&&digit<=25) temp=dp[0]+dp[1];
            else temp=dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }
};

3、网格路径（二维爬楼梯）

BM67 不同路径的数目(一)

HJ91 走方格的方案数

int uniquePaths(int m, int n) {
    //dp[i][j]表示从grid[0][0]到grid[i][j]时的最大价值
    vector<vector<int>> dp(m + 1,vector<int>(n + 1,0)) ;
    for(int i=0;i<m;i++) dp[i][0]=1;//第一行的每个位置都只有一条路径
    for(int j=0;j<n;j++) dp[0][j]=1;//第一列的每个位置都只有一条路径
    // 遍历[0,0]到[m,n]
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] =dp[i - 1][j]+ dp[i][j - 1];
        }
    }
    return dp[m-1][n-1];
}

BM68 矩阵的最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，返回最小的路径和即可。说明：每次只能向下或者向右移动一步。

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

点评

class Solution {
public:
    /* 动态规划题目
    【状态定义】dp[i][j]表示从(0,0)走到点(i-1,j-1)的最小路径和,最终求dp[m-1][n-1]
    【状态转换】dp[i][j]只能由2个方向推导而来:dp[i-1][j]、dp[i][j-1]
    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
    【初始状态】显然i正序，j正序，需要知道dp[0][0]，显然为grid[0][0]
    边界部分需要单独定义：
    dp[i][0]=dp[i-1][0] +grid[i][0];
    dp[0][j-1] +grid[0][j];
    */
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        // 初始化
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;++i) dp[i][0]=dp[i-1][0] +grid[i][0];
        for(int j=1;j<n;++j) dp[0][j]=dp[0][j-1] +grid[0][j];
        // 迭代
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

二、序列问题

1、最长递增子序列

BM71 最长上升子序列(一)

给定一个未经排序的整数数组 nums ，找到其中严格递增子序列的最长长度，子序列可以不连续。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution {
public:
    /* 动规经典问题
    【状态定义】dp[j]表示以nums[j]结尾的最长上升子序列长度
    【状态转移】对于任何的i属于[0,j-1],都有
    if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
    【初始状态】每个j对应的dp[j]都至少是1.
    */
    int LIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        // 从数组中的第2个数开始遍历,当前遍历数为i
        for (int j = 1; j < nums.size(); j++) {
            // 遍历数组中的[i,j]
            for (int i = 0; i < j; i++) {
                if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
            }
            result=max(result,dp[j]);// 保存dp数组中的最长的长度
        }
        return result;
    }
};

2、最长重复子序列

BM66 最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

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

点评

string LCS(string str1, string str2) {
    int m=str1.length();
    int n=str2.length();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    string res="";
    int len=0;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(str1[i-1]==str2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                if(len<dp[i][j]){
                    len=dp[i][j];
                    res=str1.substr(i-len,len);
                }
            }
        }
    }
    return res;
}

BM65 最长公共子序列(二)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度，如果不存在公共子序列，返回 0，公共子序列可以不连续。

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

点评

方法一：直接记下字符串，内存超限。

 string LCS(string s1, string s2) {
     int m=s1.length();
     int n=s2.length();
     vector<vector<string>> dp(m+1,vector<string>(n+1,""));
     for(int i=1;i<=m;++i){
         for(int j=1;j<=n;++j){
             if(s1[i-1]==s2[j-1]){
                 dp[i][j]=dp[i-1][j-1]+s1[i-1];
             }
             else{
                 dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
             }
         }
     }
     if(dp[m][n]=="") return "-1";
     else return dp[m][n];
 }

方法二：存长度，再反查得到字符串

string LCS(string s1, string s2) {
        int m=s1.length();
        int n=s2.length();
        // 计算长度
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
                }
            }
        }
        if(dp[m][n]==0) return "-1";
        string res="";
        for(int i=m,j=n;dp[i][j]>=1;){
            // 如果字符相等，添加进结果，并前移
            if(s1[i-1]==s2[j-1]){
                res = s1[i-1]+res;
                --i;--j;
            }
            // 如果字符不相等
            else if (dp[i-1][j]>=dp[i][j-1]) --i;
            else --j;
        }
        return res;
    }

3、最大子序列和

BM72 连续子数组的最大和

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

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

点评

int FindGreatestSumOfSubArray(vector<int> array) {
    int n=array.size();
    vector<int> dp(n,array[0]);//dp[i]表示array[i]结尾的最大连续和
    dp[0]=array[0];
    int res=dp[0];
    for(int i=1;i<n;++i){
        dp[i]=max(dp[i-1]+array[i],array[i]);
        res=max(res,dp[i]);
    }
    return res;
}

4、编辑距离

BM75 编辑距离(一)

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

点评

class Solution {
public:
    /*
    【状态定义】dp[i][j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2的最近编辑距离。
    【状态转移】dp[i][j]是由dp[i-1][j-1]、dp[i - 1][j]、dp[i][j - 1]三个方向推导而来
    具体取决于s1[i-1]和s2[i-1]的关系：
    s1[i-1]==s2[i-1]时，在s1[i-2]和s2[i-2]后面分别添加一个相同的字符，不需要操作，所以dp[i][j]=dp[i-1][j-1]
    s1[i-1]!=s2[i-1]时，增删换三选一,取最小值
        （1）尝试删除s1的一个字符：dp[i][j]=dp[i-1][j]+1:以下标i-2为结尾的s1与j-1为结尾的s2的最近编辑距离 再加上一个操作
        （2）尝试删除s2的一个字符：dp[i][j]=dp[i][j-1]+1：以下标i-2为结尾的s2与j-1为结尾的s1的最近编辑距离 再加上一个操作
        （3）尝试替换s1或者s2的一个字符：替换s1[i-1]或者s2[i-1]使其s1[i-1]==s2[i-1]
        dp[i][j]=dp[i-1][j-1]+1：以下标i-2为结尾的s1与j-2为结尾的s2的最近编辑距离 再加上一个操作
    取最小：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
    【初始状态】
    dp[i][0]表示以下标i-1为结尾的字符串word1和以下标0-1为结尾的字符串word2的最近编辑距离，其值是i
    dp[0][j]表示以下标0-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最近编辑距离，其值是j
    */
    int editDistance(string s1, string s2) {
        vector<vector<int>> dp(s1.length()+1,vector<int>(s2.length()+1,0));
        for(int i=0;i<=s1.length();++i) dp[i][0]=i;
        for(int j=0;j<=s2.length();++j) dp[0][j]=j;
        // 遍历两个字符串
        for (int i = 1; i <= s1.size(); i++) {
            for (int j = 1; j <= s2.size(); j++) {
                // 如果相等，不操作
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 如果不相等，分别尝试增删换，取最小值
                else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[s1.size()][s2.size()];
    }
};

5、回文子串

点评

方法一：暴力破解法（时间复杂度为O(n^3)）

//方法一：暴力获取所有子串
int countSubstrings(string s) {
    int res=0;
    // 遍历所有的起始位置
    for (int i = 0; i < s.length(); ++i) {
        // 遍历所有的终止位置
        for (int j = i; j < s.length(); ++j) {
            //判断子串[i,j]是否是回文串
            if (isHui(s.substr(i, j - i + 1)))res++;
        }
    }
    return res;
}
bool isHui(string s){
    int left=0;
    int right=s.length()-1;
    while(left<right){
        if(s[left]!=s[right]){
            return false;
        }
        else{
            left++;
            right--;
        }

    }
    return true;
}

方法二：动态规划法（时间复杂度为O(n^2)，空间复杂度为O(n^2)）

class Solution {
public:
    /* 回文子串，子串必须连续
    【状态定义】dp[i][j]表示字符串s在[i,j]上是否是回文子串(左右都是闭区间)
    【遍历顺序】对i是从大向小遍历，对j是从小向大遍历，则i相当于右指针，j相当于左指针
    【状态转移】
    子串长度为1，如a。这样的子串是回文子串
    子串长度为2，如aa，这样的子串要判断前后端是否相同，即s[i] == s[j]，相同则是回文子串，不相同则不是
    故有s[i]== s[j]&&j-i<=1为true时,dp[i][j] = true;
    子串长度大于2。比如 ababa 这个字符记作串1，把两边的a去掉，也就是bab记作串2，
    可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。
    所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串。
    故有s[i]== s[j]&&dp[i+ 1][j-1]为true时,dp[i][j] = true;
    【初始状态】全为true或者false都可以
    
    */
    int countSubstrings1(string s) {
        vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
        int res = 0;
        // 右指针i从大到小遍历
        for (int i=s.size()-1; i >= 0; i--) {
            // 左指针j从小到大遍历
            for (int j=i; j<s.size(); j++) {
                // 如果区间[i,j]的长度<=2，s[i]==s[j]
                if(s[i]==s[j]&&j-i<=1){
                    res++;
                    dp[i][j] = true;
                }
                // 如果区间[i,j]的长度>2,s[i]==s[j]且dp[i+1][j-1]为真
                else if(s[i]==s[j]&&dp[i+1][j-1]){
                    res++;
                    dp[i][j] = true;
                }
            }
        }
        return res;
    }
};

方法三：双指针法（时间复杂度为O(n^2)，空间复杂度为O(1)）

/*
首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候，要注意中心点有两种情况。
一个元素可以作为中心点，两个元素也可以作为中心点。
*/ 
int countSubstrings(string s) {
        int res = 0;
        // 遍历字符串s的每个字符，分别以其为中心进行扩散，
        for (int i=0; i<s.size(); i++) {
            res += extend(s, i, i, s.size()); // 以i为中心
            res += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return res;
    }
    // 从字符串s的位置i和j分别向两端扩散，
    int extend(string& s, int left, int right, int n) {
        int res=0;
        // 如果left和right扩散后仍然没有出界并且指的字符相等，
        while(left>=0&&right<n&&s[left]==s[right]) {
            left--;
            right++;
            res++;
        }
        return res;
    }

BM73 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串，如果有多个最长回文子串，随意输出一个即可。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

点评

int getLongestPalindrome(string s) {
        vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
        int maxLen = 0;
        // 右指针i从大到小遍历
        for (int i=s.size()-1; i >= 0; i--) {
            // 左指针j从小到大遍历
            for (int j=i; j<s.size(); j++) {
                // 如果区间[i,j]的长度<=2，s[i]==s[j]
                if(s[i]==s[j]){
                    if(j-i<=1||dp[i+1][j-1]){
                        dp[i][j] = true;
                        int len=j-i+1;
                        if(len>maxLen) {
                            maxLen=len;
                        }
                    }
                }
            }
        }
        return maxLen;
    }

三、背包问题

1、01背包问题

有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都只有1个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？

二维dp数组的写法

【状态定义】dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包的物品最大价值总和

【状态转移】按照是否放物品i来进行推导：

不放物品i：dp[i][j]=dp[i-1][j]

放物品i：dp[i][j]=dp[i-1][j-weight[i]]+value[i]

那么综合两种情况，取最大值：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

【初始状态】

背包容量为0时，最大价值一定都为0：dp[i][0]=0

只放入物品i=0时：

当背包容量j<weight[0]时，最大价值dp[0][j]=0

当背包容量j>=weight[0]时，最大价值dp[0][j]=value[0]

一维dp数组的写法

对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来

对于一维dp，dp[j]都是通过本层即dp[j]覆盖计算而来

【状态定义】dp[j] 表示容量为j的背包，可以放入的物品最大价值总和

【状态转移】按照是否放物品i来进行推导：

不放物品i：dp[j]=dp[j]

放物品i：dp[j]=dp[j-weight[i]]+value[i]

那么综合两种情况，取最大值：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

【初始状态】

在取最大价值时，dp数组全部初始化为0即可

剑指 Offer II 101. 分割等和子集（简单难度）

416. 分割等和子集（中等难度）

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

点评

nums的数组很大，用回溯法需要调优，很可能超时。

用动态规划法，将该问题看做一个01背包问题：

从重量为nums[i]和价值为nums[i]的一堆物品中挑选，放入容量为sum/2的背包中，问背包是否恰好装满？

/*01背包问题：本题可以理解为是否存在可以将一些重量和价值相等的物品放入容量为sum/2的背包中
    【状态定义】dp[j]表示容量为j的背包，可以放入的物品的最大总和
    【状态转移】假设放入重量为nums[i]，价值为nums[i]的物品，dp[j]放入nums[i]前的背包容量为dp[j-nums[i]]
    那么其价值为dp[j-nums[i]]+nums[i]，不放入该物品价值为dp[j]，放入该物品价值为dp[j-nums[i]]+nums[i]
    当前价值为dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
    【初始状态】dp[0]=0
    */
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int n:nums)sum+=n;
        if(sum%2!=0) return false; // 如果数组和无法被2整除则肯定无法划分
        int target=sum/2;
        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001,0);
        // 升序遍历物品
        for(int i=0;i<nums.size();++i){
            // 倒序遍历背包
            for(int j=target;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        // 如果容量为target的背包的放入物品最大总和为target
        if (dp[target] == target) return true;
        return false;
    }

1049. 最后一块石头的重量 II（中等难度）

有一堆用整数数组 stones 表示的石头，其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头最小的可能重量 。如果没有石头剩下，就返回 0。

点评

该题和1046. 最后一块石头的重量的区别是：该题要求任意挑选两块石头，返回剩下石头的最小重量；1046是每次挑选最重的两块石头，返回剩余石头的重量。显然该题已经不能使用优先级队列或者堆来解答。

一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的

所以该问题就可以转换为一个01背包问题：

在一堆重量和价值都为store[i]的物品中挑选，放入容量为sum/2的背包中，问背包最大可以容纳多少的物品

class Solution {
public:
    /* 
    一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的
    所以该问题就可以转换为一个01背包问题：
    在一堆重量和价值都为store[i]的物品中挑选，放入容量为sum/2的背包中，问背包最大可以容纳多少的物品
    */
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int stone:stones) sum+=stone;
        int target=sum/2;
        // 定义：dp[j]表示容量为j的背包最大可以容纳的石头，j的最大重量为30*100/2+1
        vector<int> dp(15001,0);
        // 遍历物品
        for(int i=0;i<stones.size();++i){
            // 降序遍历背包
            for(int j=target;j>=stones[i];--j){
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        // 此时dp[target]就是所有石头中最趋近于总重量一半的重量，sum-dp[target]是另一半的重量
        return (sum-dp[target])-dp[target];
    }
};

474. 一和零（中等难度）

给定一个二进制字符串数组 strs 和两个整数 m 和 n 。返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

点评

class Solution {
public:
    /*01背包问题：在重量为0的个数，价值为1的个数的一堆物品中，放入容量为m的价值为n的背包中
    该背包最多放入几个物品？
    【状态定义】dp[i][j]表示容量为i的、价值为j的背包的最大物品数为dp[i][j]
    【状态转换】dp[i][j]=dp[i-zeroNum][j - oneNum] + 1
    */
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        // 升序遍历物品
        for (string str : strs) { 
            int oneNum = 0, zeroNum = 0;
            // 统计0和1的数字
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            // 降序遍历背包
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

2、完全背包问题

一维数组的写法

有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都有无数个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？相关模板：

// 先遍历背包，再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    // 初始化dp数组
    vector<int> dp(bagWeight + 1, 0);
    // 升序遍历物品体积
    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]);
        }
    }
    cout << dp[bagWeight] << endl;
}

在完全背包中，遍历物品体积和遍历背包容量的先后顺序无所谓

排列数和组合数

vector<int> dp(target + 1, 0);
dp[0] = 1;
// 先遍历背包+后遍历物品，得到排列数
for (int j = 0; j <= target; j++) { 
    for (int num:nums) { 
        if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
            dp[j] += dp[j - num];
        }
    }
}
// 先遍历物品+后遍历背包，得到组合数
for(int num:nums){
    for(int j=num;j<=target;j++){
        dp[j]+=dp[j-num];
    }
}
return dp[target];

322. 零钱兑换（中等难度）

给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

点评

假设有面值为 1, 2, 5 的硬币，原问题是求 amount 时的最少硬币数，

就是求 amount-1，amount-2，amount-5 的三个子问题中的最少硬币数，然后加一（再选一枚面值为 1, 2, 5 的硬币），这就是原问题的答案。

因为硬币数量没有限制，所以子问题之间没有相互制约，相互独立，即符合最优子问题。

class Solution {
public:
    /* 假设有面值为 1, 2, 5的硬币，原问题是求金额i时的最少硬币数，
    就是求 i-1，i-2，i-5 的三个子问题中的最少硬币数，
   然后加一（再选一枚面值为 1, 2, 5 的硬币）
    因为硬币数量没有限制，所以子问题之间没有相互制约，相互独立，即符合最优子问题。
    dp(i)=min(dp(i-1)+1,dp(i-2)+1,dp(i-5)+1)
    【定义dp】凑足总额为i的所需钱币最少个数为dp[i]
    【状态转移】凑足总额为i的所需钱币最少个数为dp[i]=min(dp[i],1+dp[i-coin[j]]),j负责遍历coin数组
    【初始条件】dp[0]=0，dp[-1]=-1，
    */
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount+1);//数组大小为amount+1，初始值为一个比该题目中答案都大的值
        dp[0] = 0;
        // 遍历所有的硬币的选择（物品）
        for (int coin:coins) { // 遍历物品
            // 遍历所有的amount（背包）
            for (int i = 0; i < amount+1; i++) { 
                // 如果子问题有解
                if (i- coin>=0) { 
                    dp[i] = min(dp[i],1+dp[i -coin]);
                }
            }
        }
        // 如果硬币没法凑出金额，那么dp[amount]为初始值
        if (dp[amount] == amount+1) return -1;
        return dp[amount];
    }
};

518. 零钱兑换 II（中等难度）

给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的硬币组合的个数。如果没有任何一种硬币组合能组成总金额，返回 0。

输入：coins = [1, 2, 5], amount = 5
输出：4
解释：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

点评

转换为背包形式：有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。

下面就以背包问题的描述形式，继续按照流程来分析。

class Solution {
public:
   /* 完全背包问题:向容量为amount的背包放入不同种类的体积和价值都为coins[i]的物品
   【状态定义】dp[j]表示可以凑出金额j的组合个数（不强调元素之间的顺序）
   【状态转移】在容量为j的背包里放第i个硬币coins[i]
       放第i个硬币的组合数：dp[j]=dp[j-coins[i]];// 容量为j的组合数和容量为j-coins[i]的组合数一样
       不放第i个硬币的组合数：dp[j]=dp[j]//使用(0,i-1)的结果
       综合来看共有dp[j]=dp[j]+dp[j-coins[i]];
    【初始状态】dp[0]=1
    【遍历顺序】先物品后背包
   */
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0]=1;
        // 升序遍历所有物品
        for(int coin:coins){
            // 升序遍历所有背包容量
            for(int j=coin;j<=amount;j++){
                dp[j]+=dp[j-coin];
            }
        }
        return dp[amount];
    }
};

494. 目标和（中等难度）

给定一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式，求共有几种表达式

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

点评

这题可以用回溯法，这里讲解动态规划法

原问题等同于：找到nums一个正子集P和一个负子集N，使得总和等于target

假设nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是+1-2+3-4+5 = 3

这里正子集P = [1, 3, 5]和负子集N = [2, 4]

那么sum(P) - sum(N) = target，sum(P) +sum(N) = sum(nums) ，可以得到：

sum(P) = （target + sum(nums)）/2，其中target + sum(nums)必须为偶数，否则不存在

该问题转换为：价值和重量都为nums[i]的物品中，放入容量为sum(P) 的背包中，问背包中的物品个数

 /*01背包问题：用价值与体积均为nums[i]的物品,恰好凑满容量为(target+sum)/2的背包方案数：装几件物品
    【状态定义】dp[j]为恰好能凑满容量为j的背包方案数
    【状态转移】背包容量能或者不能装下nums[i]：
        2.1 当不能装下nums[i]时,方案数直接继承之前的dp[j]
        2.2 当能装下nums[i]时,总的方案数为不考虑nums[i]的方案数+有nums[i]参与新增的方案数
            dp[j] += dp[j - nums[i]],dp[j - nums[i]]种方案与nums[i]共同凑成pos,即1*dp[j - nums[i]]
    【状态初始】装满容量为0的背包，有1种方法，就是装0件物品。
    */
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int n:nums) sum+=n;
        if (abs(target) > sum) return 0; // 此时没有方案
        if((target+sum)%2!=0) return 0; // 此时没有方案
        int bagSize=(target+sum)/2;
        vector<int> dp(bagSize+1,0);
        dp[0]=1;
        // 升序遍历物品
        for(int i=0;i<nums.size();++i){
            // 降序遍历背包
            for(int j=bagSize;j>=nums[i];--j){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }

70. 爬楼梯（简单难度）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    /* 完全背包问题：容量为n的背包中放入体积为1或2的物品，问背包中放入物品的排列数
    */
    int climbStairs(int n) {
        vector<int> weights={1,2};
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int j=0;j<=n;++j){
            for(int weight:weights){
                if(j-weight>=0){
                    dp[j]=dp[j]+dp[j-weight];
                }
            }
        }
        return dp[n];
    }
};

377. 组合总和 Ⅳ（中等难度）

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。注意，数组nums中的每个数组可以使用多次，顺序不同的序列是做不同的组合。

输入：nums = [1,2,3], target = 4 输出：7 解释：所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 点评

/* 完全背包问题：向容量为target的背包中放入体积和价值都为nums[i]的物品
    问恰好放满背包的排列数量？
    【状态定义】dp[j]表示容量为j的背包恰好放满的数量
    【状态转移】dp[j]=dp[j]+dp[j-nums[i]]
    【初始状态】dp[0] = 1
    【遍历顺序】先背包后物品，注意dp[j] < INT_MAX - dp[j - num]
    */
int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    // 升序遍历所有的背包容量
    for (int j = 0; j <= target; j++) { 
        // 升序遍历所有的物品体积
        for (int num:nums) { 
            if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
                dp[j] =dp[j]+ dp[j - num];
            }
        }
    }
    return dp[target];
}

279. 完全平方数（中等难度）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数可以重复。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

class Solution {
public:
    /*完全背包问题： 向一个容积为n的背包中放入体积为完全平方数的物品，问背包中恰好放满时的物品的最少数量
    【状态定义】dp[j]表示容量为j的背包恰好放满的最少物品数量
    【状态转移】对于第i个物品：
    不放入：dp[j]=dp[j]
    放入：dp[j]=dp[j-weight[i]]+1
    综上：dp[j]=min(dp[j],1+dp[j-weight[i]])
    【初始状态】dp[0]=0
    */
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);// 取最小值，则初始值必须为最大值
        dp[0]=0;
        // 遍历物品
        for(int i=1;i*i<=n;i++){
            int weight=i*i;
            // 遍历背包容量
            for(int j=1;j<=n;j++){
                if(j-weight>=0){
                    dp[j]=min(dp[j],1+dp[j-weight]);
                }
            }
        }
        return dp[n];
    }
};

139. 单词拆分（中等难度）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

class Solution {
public:
    /* 完全背包问题：容量为s的背包中放入体积为wordDict的物品
    【状态定义】dp[j]表示s的长度为i时，可以拆分字典中的单词为j的背包是否可以恰好放入物品
    【状态转移】对于物品wordDict[i]
    如果原来的dp[j] 是true，且 [i, j] 这个区间的子串出现在字典里，那么dp[j]一定是true。（i < j ）。
    【初始状态】dp[0]=true
    */
    bool wordBreak(string s, vector<string>& wordDict) {
        // 将单词字典存入哈希集合
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // 动态数组
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        // 遍历所有的物品
        for (int i = 0; i < s.size(); i ++){ 
            // 遍历所有的字符串的长度
            for (int j = i; j <= s.size(); j++){       // 遍历物品
                string word = s.substr(i, j - i); //substr(起始位置，截取的个数)
                // 如果单词字典中存在该单词并且上一个区间也是true
                if (wordSet.count(word)&& dp[i]) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

四、股票问题

剑指 Offer 63. 股票的最大利润（中等难度）

121. 买卖股票的最佳时机（简单难度）

2016. 增量元素之间的最大差值（简单难度）

class Solution {
public:
    /*解析：
    股票问题是动态规划的经典应用场景，本题是股票类中最简单的一个问题
    买卖一次股票的最大利润意味着必须在股票价格最小值买入，最小值之后的股票价格最大值卖出。
    本题只要求出最小值，和最小值之后的最大值就能通过。
    但是我们重点放在动态规划的思路上：
    【状态定义】：dp[i] 表示的含义为价格数组中0-i的子数组的最大利润,i<n
    【转移方程】：假设
    前n天的最大利润 = max(前n-1天的最大利润，第n天的价格 - 前n天的最低价格)
    dp[i] = max(dp[i-1], min(prices[n], minCost))
    【初始状态】： dp[0] = 0
    */
    int maxProfit1(vector<int>& prices) {
        int minCost = INT_MAX;
        int res=0;
        for(int price:prices){
            minCost = min(minCost,price);
            res=max(res,price-minCost);
        }
        return res;
    }
    class Solution {
public:
    /* 该题只可以买卖一次股票，那么一定是在价格最低点买入，价格最高点卖出时利润最大
    本质上是求一个整数数组内最大值和最小值的差
    动态规划
    【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出
    但是这3个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后
    对应有2个状态，持有和不持有，所以dp可以看做是[n,2]维度
    dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
    注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
    【状态转换】
    dp[i][0]=max(dp[i-1][0], -prices[i]);// 第i天继续持有，第i天新买入（前期卖出利润（0）-当前价格）
    dp[i][1]=max(dp[i-1][1], prices[i]+dp[i-1][0]);// 第i天不继续持有，第i天新卖出（前期买入利润+当前价格）
    【初始状态】
    dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
    dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
    【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
    */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1] = 0;
        for(int i=1;i<n;++i){
            dp[i][0]=max(dp[i-1][0], -prices[i]);
            dp[i][1]=max(dp[i-1][1], prices[i]+dp[i-1][0]);
        }
        return dp[n-1][1];
    }
};
};

122. 买卖股票的最佳时机 II（中等难度）

给定一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。求你能获得的最大利润。

输入：prices = [7,1,5,3,6,4] 输出：7 解释：

在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 获得利润 5 - 1 = 4 。在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 获得利润 6 - 3 = 3 。总利润为 4 + 3 = 7 。

点评

最大利润一定是在每次股票上涨前买入，下跌前卖出。

方法一：双指针法

/*该题可以多次买卖股票，那么一定是在价格上升前买入，价格下降前卖出利润最大
本质上是求一个整数数组内所有上升区间的累加和*/ 
int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int res=0;// 结果
        int begin=0;// 递增区间的起始位置
        int end=0;// 递增区间的结束位置
        // 遍历数组，查找所有递增区间，累加prices[end]-prices[begin]
        for(int i=1;i<n;++i){
            // 如果当前数是递增的
            if(prices[i]>prices[i-1]){
                end++;// 结束指针移动
                // 如果当前位置是数组最后一个，添加最后一个递增区间
                if(i==n-1){
                    res+=prices[end]-prices[begin];
                }
            }
            // 如果当前数是非递增的
            else{
                // 添加之前的递增区间
                res+=prices[end]-prices[begin];
                // 重置递增区间
                begin=i;
                end=i;
            }
        }
        return res;
    }

方法二：动态规划法

class Solution {
public:
    /* 该题可以多次买卖股票，那么一定是在价格上升前买入，价格下降前卖出利润最大
    本质上是求一个整数数组内所有上升区间的累加和
    动态规划：
    【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出
    但是这3个操作不是相互独立的，初次买入必须在不操作后，再次买入必须在卖出后，卖出必须在买入后
    可以对应有2个状态，持有股票和不持有股票，所以dp可以看做是[n,2]维度
    dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
    注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
    【状态转换】
    因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
    如果只能买卖一次，第i天手中买入说明前期都没有利润
    dp[i][0]=max(dp[i-1][0], dp[i-1][1]-prices[i]);// 第i天继续持有，第i天新买入，必须在第i-1天没有持有时操作（前期卖出利润-当前价格）
    dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]);//  第i天不继续持有，必须在第i-1天有持有时操作，第i天新卖出（前期买入利润+当前价格）
    【初始状态】
    dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
    dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
    【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
    */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1] = 0;
        for(int i=1;i<n;++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[n-1][1];
    }
};

714. 买卖股票的最佳时机含手续费（中等难度）

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润:
在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

点评

class Solution {
public:
    /* 该题可以多次买卖股票，但是每笔交易都需要额外的手续费
    动态规划：
    【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出（同时支付手续费）
    但是这3个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后
    可以对应有2个状态，持有股票和不持有股票，所以dp可以看做是[n,2]维度
    dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
    注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
    【状态转换】
    因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
    如果只能买卖一次，第i天手中买入说明前期都没有利润
    dp[i][0]=max(dp[i-1][0], dp[i-1][1]-prices[i]);// 第i天继续持有，第i天新买入，必须在第i-1天没有持有时操作（前期卖出利润-当前价格）
    dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]-fee);// 第i天不继续持有，必须在第i-1天有持有时操作，第i天新卖出（前期买入利润+当前价格）
    【初始状态】
    dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
    dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
    【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
    */
    int maxProfit(vector<int>& prices,int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1] = 0;
        for(int i=1;i<n;++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]-fee);
        }
        return dp[n-1][1];
    }
};

123. 买卖股票的最佳时机 III（困难难度）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

点评

class Solution {
public:
    /* 该题可以最多2次买卖股票
    本质上是求一个整数数组内所有上升区间中最大的两个上升区间的累加和
    注意：这两个上升区间中允许存在小范围的下降，所以判断上升区间变得比较难
    动态规划：
    【状态定义】prices中的每个数字都有5个状态，
    0（没有操作）1（第1次买入）2（第1次卖出）3（第2次买入）4（第2次卖出）
    这5个操作不是相互独立的，0必须在0基础上操作，1必须在0之后操作，2必须在1之后操作，3必须在2之后操作，4必须在3之后操作
    对应5种状态，设dp是[n,5]维度
    dp[i][0]表示第i天没有操作的利润，该值恒为0
    dp[i][1]表示第i天持有的股票利润，此时可能是第1次新买入，也可能没有操作（第i-1天就持有股票）
    dp[i][2]表示第i天不持有的股票利润，此时可能是第1次新卖出，也可能没有操作（第i-1天就不持有股票）
    dp[i][3]表示第i天持有的股票利润，此时可能是第2次新买入，也可能没有操作（第i-1天就持有股票）
    dp[i][4]表示第i天不持有的股票利润，此时可能是第2次新卖出，也可能没有操作（第i-1天就不持有股票）
    【状态转换】
    因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
    dp[i][0]=dp[i-1][0];//第i天什么也不操作，沿用上次
    dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);// 第i天继续持有或第i天第1次新买入
    dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出
    dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i]);// 第i天继续持有或第i天第2次新买入
    dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i]);// 第i天不继续持有或第i天第2次新卖出
    【初始状态】
    dp[0][0]表示第0天没有操作，dp[0][0]=0
    dp[0][1]表示第0天持有股票，此时持有股票一定就是第1次买入股票了，dp[0][1]=-prices[0];
    dp[0][2]表示第0天不持有股票，此时持有股票一定就是第1次卖出股票了，因为不可以未买先卖，dp[0][2] = 0;
    dp[0][3]表示第0天持有股票，此时持有股票一定就是第2次买入股票了，dp[0][3]=-prices[0];
    dp[0][4]表示第0天不持有股票，此时持有股票一定就是第2次卖出股票了，因为不可以未买先卖，dp[0][4] = 0;
    【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出*/
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(5,0));
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];
        for(int i=1;i<n;++i){
            //dp[i][0]=dp[i-1][0];//第i天什么也不操作，可以不写，因为都是0
            dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);// 第i天继续持有或第i天第1次新买入（前期卖出利润-当前价格）
            dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出（前期卖出利润+当前价格）
            dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i]);// 第i天继续持有或第i天第2次新买入（前期买入利润-当前价格）
            dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i]);// 第i天不继续持有或第i天第2次新卖出（前期买入利润+当前价格）
        }
        return dp[n-1][4];
    }
};

188. 买卖股票的最佳时机 IV（困难难度）

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

点评

class Solution {
public:
    /* 该题可以最多k次买卖股票
    是123的扩展版，可根据123题的答案找出规律*/
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(2*k+1,0));
        for (int j = 1; j < 2*k; j +=2) {
            dp[0][j]=-prices[0];
        }
        for(int i=1;i<n;++i){
            for (int j = 0; j < 2 * k - 1; j += 2) {
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);// 第i天继续持有或第i天第1次新买入（前期卖出利润-当前价格）
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出（前期卖出利润+当前价格）
            }
        }
        return dp[n-1][2*k];
    }
};

309. 最佳买卖股票时机含冷冻期（中等难度）

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

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

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

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

点评

 /* 该题可以多次买卖股票，但是每次卖出股票后都无法继续操作
    动态规划：
    【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出、冷冻期
    这4个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后，冷冻期必须在卖出后且只能为1天
    可以对应有4个状态，dp可以看做是[n,4]维度：
    0(今天持有股票：可能是今天新买入，也可能是之前就买入了股票然后没有操作)
    1(今天不持有股票：昨天就不持有股票今天没有操作，之后不是冷冻期)
    2(今天不持有股票：昨天持有股票今天卖出，之后是冷冻期)
    3(今天为冷冻期，不可以买卖)
    dp[i][0]表示第i天为状态0的利润
    dp[i][1]表示第i天为状态1的利润
    dp[i][2]表示第i天为状态2的利润
    dp[i][3]表示第i天为状态3的利润
    【状态转换】
    状态转换：0、1、3—>0；1、3—>1；0—>2；2—>3
    0持有股票状态的三种情况：
        昨天就持有股票今天没有操作,在状态0上继续沿用：dp[i][0]=dp[i-1][0]
        昨天是冷冻期今天新买入，在状态3上减去费用：dp[i][0]=dp[i-1][3]-prices[i]]
        昨天不是冷冻期今天新买入，在状态1上减去费用：但前一天不是冷冻期,在状态1上减去费用：dp[i][0]=dp[i-1][1]-prices[i]
    综上dp[i][0] = max(dp[i - 1][0], max(dp[i-1][3], dp[i-1][1])-prices[i]);
    1今天不持有股票：昨天就不持有股票今天没有操作，之后不是冷冻期
    昨天就是状态二或者昨天是冷冻期，即状态3
    dp[i][1] = max(dp[i-1][1], dp[i-1][3]);
    2今天不持有股票：昨天持有股票今天卖出，之后是冷冻期，在装填0的基础上操作：
    dp[i][2] = dp[i-1][0] + prices[i];
    3今天是冷冻期，不可以买卖，沿用状态2：
    dp[i][3] = dp[i-1][2];
    【初始状态】
    dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
    dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
    【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
    */

五、打家劫舍问题

本博客是记录作者做动态规划算法的和打家劫舍相关的中等难度题的笔记。

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
198	打家劫舍（中等难度）	一排有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额	dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]，决定dp[i]的因素就是第i房间偷还是不偷。	198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)
213	打家劫舍II（中等难度）	一圈有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额	当有多余两间房的时候：考虑首位相连问题。取了第一间房，就不能要最后一间房：[0, n-2] ；取了最后一间房，就不能要第一间房：[1, n-1]；对这两段用普通的打家劫舍算法，再取这两段的最大值返回。	213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)
337	打家劫舍III（中等难度）	二叉树形状的动态规划，父子节点不能同时偷	偷当前节点,左右孩子就都不能偷，偷当前节点，左右孩子可以偷也可以不偷；递归函数返回一个长度为2的数组，0：不偷，1：偷	337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

198. 打家劫舍

这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。

以[1,2,3,1]为例，为了不触发警报，小偷可以选择1，3和2，1，比较其谁更大就选择谁

假设dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。，显然

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

代码如下：

 /*这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。
    以[1,2,3,1]为例，为了不触发警报，小偷可以选择1，3和2，1，比较其谁更大就选择谁
    假设dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。显然
    决定dp[i]的因素就是第i房间偷还是不偷。
    如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，
    即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
    如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房（注意这里是考虑，并不是一定要偷i-1房）
    然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);*/
    int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size());//dp[i]表示加上第i个房屋后一共可以盗窃的最大金额
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        // 推导dp数组
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.size()-1];
    }

213. 打家劫舍 II

这道题目的关键是明白第n个台阶只能从第n-1或者n-2个上来，所以到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法。

/*这道题目的关键是明白
    第n个台阶只能从第n-1或者n-2个上来，
    所以到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法。
    思路如下：
        1. 当只有一间房的时候，直接返回这个返回金额。
        2. 当有两间房的时候，返回这两个房间的最大值。
        3. 当有多余两间房的时候：考虑首位相连问题。
            取了第一间房，就不能要最后一间房：[0, n-2]
            取了最后一间房，就不能要第一间房：[1, n-1]
        对这两段用普通的打家劫舍算法，再取这两段的最大值返回。
    */
    int rob(vector<int>& nums){
        if(nums.size()==1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 取了第一间房，就不能要最后一间房：[0, n-2]
        int result2 = robRange(nums, 1, nums.size() - 1); // 取了最后一间房，就不能要第一间房：[1, n-1]
        return max(result1, result2);
    }
    
    int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());//动归数组
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }

337. 打家劫舍 III

整理后的代码如下：

// 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷当前节点,左右孩子就都不能偷
        int val1 = cur->val + left[0] + right[0];
        // 不偷当前节点，左右孩子可以偷也可以不偷
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }

六、剪绳子问题

343. 整数拆分（中等难度）

剑指 Offer 14- I. 剪绳子（中等难度）

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

点评

class Solution {
public:
    /*解析：本题是将一个整数n拆分成若干个数字之和，并且使这几个数字之积最大
    分析：
    结论1：至少剪下长度为2的绳子
    对任意长度n的绳子都不应该剪下长度为1的绳子，因为1和任何数相乘都是哪个数本身：n>(n-1)*1
    结论2：求长度为n的绳子剪掉后的最大乘积与求长度为n-1、n-2、n-3的绳子的最大乘积的思路一致
    本题是求最优解问题，如乘积最大，该问题可以划分为若干子问题，例如剪一刀后，剩余剪的问题和之前性质一致
    【状态定义】：dp[i] 表示长度为i的绳子剪成m段后的最大乘积
    【转移方程】：
    假设剪一刀，绳子变为2段，第一段是长度为j，第二段的长度为i-j，其乘积为j*(i-j)，2<=j<n
    那么要不要继续剪第二刀或者第三刀呢？不确定
    如果不剪的话，总的乘积就是j*(i-j)
    如果剪的话，不清楚剪几刀，索性第二段的最大乘积表示为dp[i-j]，总的乘积为j*dp[i-j]
    那么最终剪不剪，取决于最大值:
    则本次剪的最大乘积为max(j*(i-j),j*dp[i-j]);2<=j<i
    由于j的取值需要遍历，即不清楚第一刀j是多少，只能保留最大值
    dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));//第一刀剪j-1和第一刀剪i之间取足底啊之
    【初始状态】：
    首先考虑边界问题，已知绳子最少应该剪下长度为2的的小段，那么长度为1、2的绳子就是边界问题
    绳子必须被剪一刀，所以绳子为2时，其只能是分成1和1
    dp[2]=1;
    */
    int cuttingRope(int n) {
        if(n<=1) return 1;//实际上测试数据中n>=2
        vector<int> dp(n+1,0);//动规数组，dp[i] 表示长度为i的绳子剪成m段后的最大乘积
        dp[2]=1;//长度为2的绳子只能剪成1和1，所以最大乘积是1
        // 推导长度为[3,n]的绳子的最大乘积
        for(int i=3;i<=n;i++){
            // 剪第一刀，分为j和i-j，j的大小应该在[2,i）
            for(int j=2;j<i;j++){
                // 如果不剪，乘积为j*(i-j)，如果继续剪更多刀，乘积为j*dp[i-j]
                int temp=max(j*(i-j),j*dp[i-j]);// 第一刀剪j的最大乘积
                dp[i]=max(dp[i],temp);//绳子为i的最大乘积，j不同情况下的最大值
            }
        }
        return dp[n];
    }
};

剑指 Offer 14- II. 剪绳子 II（中等难度）

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

点评

class Solution {
public:
    /*解析：本题是将一个整数n拆分成若干个数字之和，并且使这几个数字之积最大
    和[剑指 Offer 14- I. 剪绳子（中等难度）]的区别在于n的测试数据变得更大，需要对答案取模。
    C++中取余之后max函数就不能用来比大小，不可以继续使用动态规划法,难点在于大数运算
    经过数学推导可知：
    ① 当所有绳段长度相等时，乘积最大。
    ② 最优的绳段长度为 3 。
    用贪心的思想，尽可能地多切出点长度为3的绳子，对于最后的切法，要考虑到整体长度：
    （1）如果绳子长度为2，切1和1
    （2）如果绳子长度为3，切2和1
    （2）如果绳子长度为3的倍数，全部切3
    （3）如果绳子长度为3的倍数+1，则切若干3，剩余4
    （4）如果绳子长度为3的倍数+2，则切若干3，剩余2
    */
    int cuttingRope(int n) {
        if(n<=3) return n-1;//实际上测试数据中n>=2
        long res = 1;// 乘积
        // 将n减去若干个3，直至n<=4,n=2、3、4
        while (n > 4) {
            n -= 3;
            res *= 3;
            res %= 1000000007;
        }
        // 乘以剩余段长
        res=res * n % 1000000007;
        return res;
    }
};

七、其他问题

1、二叉树问题

96. 不同的二叉搜索树（中等难度）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。n的范围在[1,19]

输入：n = 3
输出：5

点评

class Solution {
public:
    /*动态规划题
    【状态定义】dp[i]表示i个节点的二叉搜索树的个数
    【状态转换】以dp[3]为例，dp[3]=元素1为根的个数+元素2为根的个数+元素3为根的个数
    元素1为根的个数=右子树有2个元素的个数*左子树有0个元素的个数=dp[2]*dp[0]
    元素2为根的个数=右子树有1个元素的个数*左子树有1个元素的个数=dp[1]*dp[1]
    元素3为根的个数=右子树有0个元素的个数*左子树有2个元素的个数=dp[0]*dp[2]
    得dp[3]==dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]
    假设j为根节点个数，范围在[1,i]
    则 dp[i]+=元素j为根的个数
    =右子树有i-j个元素的个数*左子树有j-1个元素的个数
    =dp[i-j]*dp[j-1]
    【初始状态】根据递推公式，dp[0]需要初始化
    dp[0]表示0个节点的二叉搜索树的个数，可以视为空树，设为1
    【遍历顺序】根据递推公式，dp[i]的推导依赖于j，dp[i-j]在dp[i]之前得出
    所以i的范围是正序，在[1,n]，j不能超过i，范围在[1,n]
    */
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        // i表示节点数,范围在[1,n]
        for (int i = 1; i <= n; i++) {
            // j表示j为根时的情况，范围在[1,i]
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];// 递归公式
            }
        }
        return dp[n];
    }
};

95. 不同的二叉搜索树 II（中等难度）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回所有满足题意的二叉搜索树。n的范围在[1,8]

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

点评

该题和96的不同点在于，其需要返回所有不同的二叉搜索树，其n的范围缩小到8，就减少了计算量，可以用深度优先搜索。96中的动态规划无法用来求解该题。

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int start,int end){
        if(start>end) return {nullptr};
        vector<TreeNode*> resTrees;
        // 遍历所有为n的节点，作为当前的根节点
        for(int i=start;i<=end;++i){
             // 获得所有可行的左子树集合
            vector<TreeNode*> leftTrees = dfs(start, i - 1);
            // 获得所有可行的右子树集合
            vector<TreeNode*> rightTrees = dfs(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (auto& left:leftTrees) {
                for (auto& right:rightTrees) {
                    TreeNode* currTree = new TreeNode(i);
                    currTree->left = left;
                    currTree->right = right;
                    resTrees.emplace_back(currTree);//加入当前节点
                }
            }
        }
        return resTrees;
    }
};

2、丑数问题

剑指 Offer 49. 丑数（中等难度）

264. 丑数 II（中等难度）

class Solution {
public:
    /* 解析：本类型题是动态规划问题，属于特殊情景类，根据题意设计算法
    【状态定义】：dp[i]表示的含义为从小到大排序的第i个丑数
    【转移方程】：
    理论原理：
    最小的丑数是1，即dp[1]=1，那么如何得到其他的丑数呢？
    任意一个丑数都是由小于它的某一个丑数*2，*3或者*5得到的，假设存在3个有序数组分别是每个丑数*2，*3或者*5
    那么所有丑数的排列，必定就是上面ABC3个有序数组的合并结果然后去重得到的

    假设有3个有序数组A={1*2}，B={1*3}，C={1*5}，定义三个指针，p2,p3,p5分别指向其中第一个元素。
    dp[2]=min(A[p2],B[p3],C[p5])=2;
    A={1*2,2*2}，B={1*3,2*3}，C={1*5,2*5}...
    可以发现，ABC三个数组实际上就是dp[]*2，dp[]*3和dp[]*5的结果，
    dp[i]=min(A[p2],B[p3],C[p5]),谁的最小就移动谁的指针
    合并有序数组的一个比较好的方法，就是每个数组都对应一个指针，
    然后比较这些指针所指的数中哪个最小，就将这个数放到结果数组中，然后该指针向后挪一位。
    */
    int nthUglyNumber(int n) {
        vector<int> dp(n+1,0);//动规数组
        dp[1]=1;//初始状态
        int p2=1,p3=1,p5=1;//三个指针中的初始值
        // 遍历[2,n]
        for(int i=2;i<=n;i++){
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = min(min(num2, num3), num5);//取三个有序数组中的最小值
            // 谁的最小谁的指针就移动（合并3个有序数组的操作）
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n];
    }
};

3、约瑟夫环问题

剑指 Offer 62. 圆圈中最后剩下的数字（简单难度）

class Solution {
public:
    /* 本题是根据经典的约瑟夫环的数学问题设计而来的，
    N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
    解决方案：
    模拟法：普通的模拟方式就是使用循环链表，按照题意进行模拟，其时间复杂度高达O(nm)
    动态规划法：
    【状态定义】：dp[i] 表示的含义为有i个数，每次删除第m个数后的剩余数字索引,i<n
    【转移方程】：假设有8个数，每次删除第3个数：
    索引：0 1 2 3 4 5 6 7
         1 2 [3] 4 5 6 7 8
         4 5 [6] 7 8 1 2 
         7 8 [1] 2 4 5 
         2 4 [5] 7 8
         7 8 [2] 4 
         4 7 [8]
        [4]7
         7 最终的胜利者
    通过观察上述过程，可知，每删除一个数字，相当于将胜利者的索引前移了m位
    已知i-1个人时，胜利者的下标位置dp[i-1]
    i个人时，胜利者的索引相当于往后移动M位，由于移动后数组可能越界，
    如果超出，则超出的部分接到头部，索引则需要对数字个数i取模
    dp[i]=(dp[i-1]+m)%i，
    【初始状态】： dp[1] = 0
    */
    int lastRemaining(int n, int m) {
        vector<int> dp(n+1,0);
        dp[1]=0;
        for (int i = 2; i <=n; i++) {
            dp[i]=(dp[i-1]+m)%i;
        }
        return dp[n];

    }
};

4、乘积数组

剑指 Offer 66. 构建乘积数组（中等难度）

238. 除自身以外数组的乘积（中等难度）

class Solution {
public:
    /*解析：本题的题意不难理解，最简单的思路就是用2个循环暴力破解
    但是注意到a的长度最多100000，而且不让用除法，所以暴力破解法大概率会超时。
    */
    vector<int> constructArr(vector<int>& a) {
        // 方法一：暴力破解法（超时）
        // int n=a.size();
        // vector<int> res(n,1);
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         if(j!=i) res[i]*=a[j];
        //     }
        // }
        // return res;
        // 方法二：
        int n=a.size();
        vector<int> res(n,1);
        int left=1;
        for(int i=0;i<n;i++){
            res[i]=left;
            left*=a[i];
        }
        int right=1;
        for(int i=n-1;i>=0;i--){
            res[i] *= right;
            right *= a[i]; 
        }
        return res;
    }
};

152. 乘积最大子数组（中等难度）

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位整数。

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

点评

首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况：

如果该元素为正数：
- 如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大
- 如果到上一个元素为止的最大乘积是负数，那么最大乘积就会变成该元素本身，且连续性被断掉
如果该元素为负数：
- 如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大
- 如果到上一个元素为止的最大乘积是正数，那么最大乘积就会不变，且连续性被断掉

以上四种情况中说到的最大乘积都是临时最大乘积，每遍历新的元素都需要进行比较来确定真正的最大乘积。

如果细心的话就可以发现，如果要得到乘以当前元素以后的最大乘积，需要记录最大乘积，也要记录最小乘积，因为最小值可能翻身变最大值。

class Solution {
public:
    /* 找出最大乘积子序列，子序列必须连续
    该题的难点在于序列中存在负数，在乘积中会让原来最大的变最小的，最小的变最大的
    注意和53题区分
    （1）假设不存在负数，imax表示i之前的最大乘积,对于nums[i],分2种情况讨论：
    如果乘nums[i],那么imax = imax*nums[i];
    如果不乘nums[i],那么由于子序列的连续性,之前的子序列不能再使用,
    i作为新的子序列中的第一个数,重新计算乘积imax = nums[i];
    综合,imax = max(imax*nums[i], nums[i]); 
    （2）由于存在负数，nums[i]<0时,会让之前的连续子序列最小乘积（负数）变为最大值
    所以需要同时维护一个最小乘积：imin = min(imin*nums[i], nums[i]); 
    当nums[i]<0时，交换imin 和imax 的值
    */
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        int maxRes = INT_MIN;
        int imax = 1, imin = 1;// 保存最大值和最小值
        for(int i=0; i<n; i++){
            // 如果当前数是负数,在乘积中会让原来最大的变最小的，最小的变最大的
            if(nums[i]<0) swap(imax, imin);
            imax = max(imax*nums[i], nums[i]);// 记录此时的最大值
            imin = min(imin*nums[i], nums[i]);// 记录此时的最小值，辅助 
            maxRes = max(maxRes, imax);// 保存最大值
        }
        return maxRes;
    }
};

5、骰子问题

剑指 Offer 60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

点评

class Solution {
public:
    /* 解析：每个骰子可以投出1-6个数，n个骰子的点数和的范围为[n,6n].
    如果采用暴力统计方式，则需要遍历6^n个组合，统计出每个点数和的次数/6^n，显然运算非常大。
    第1个骰子投出的每个点数的概率相等，均为1/6，
    第2个骰子投出后，会影响之前已投出的每个点数的概率
    【状态定义】：dp[i][s] 表示i个骰子投出s点的次数
    【状态转移】：
    第i个骰子会投出[1,6]点，则第i-1个骰子需要投出[s-1,s-6]点，就可以使第i个骰子投出s点
    dp[i][s]=dp[i-1][s-1]+dp[i-1][s-2]+dp[i-1][s-3]+dp[i-1][s-4]+dp[i-1][s-5]+dp[i-1][s-6]
    【初始状态】：
    1个骰子投出和为[1,6]的次数都是1，即
    for (int i = 1; i <= 6; i++) dp[1][i] = 1;
    */
    vector<double> dicesProbability(int n) {
        //【状态定义】：dp[i][s] 表示i个骰子投出s点的次数，i的范围是[1,n],s的范围是[n,6n]
        vector<vector<double>> dp(n+1,vector<double>(6*n+1,0));
        //【初始状态】：1个骰子投出和为[1,6]的次数都是1
        for (int i = 1; i <= 6; i++) dp[1][i] = 1;
        // i 表示骰子数,
        for (int i = 2; i <= n; i++) {
            // s 表示 i 个骰子投出的点数
            for (int s = i; s <= 6 * i; s++) {
                // cur 表示第 i 个骰子投出的点数
                for (int cur = 1; cur <= 6; cur++) {
                    // s - cur 表示前 i - 1 个骰子应该投出的点数
                    // 前 i - 1 个骰子投出的点数最小值为 i - 1
                    // 如果 s - cur 小于 i - 1 说明不可能
                    if (s - cur < i - 1) break;
                    dp[i][s] += dp[i - 1][s - cur];
                }
            }
        }
        double total = pow(6, n);// 总共的组合次数
        // 点数和s取值[n,6n]，总共有 6n - n + 1 = 5n + 1个
        vector<double> res(5 * n + 1);//表示点数和s为[n,6n]的概率：dp[n][i] / total
        for (int i = n; i <= 6 * n; i++) res[i - n] = dp[n][i] / total;
        return res;
    }
};

6、正方形问题

221. 最大正方形（中等难度）

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

点评

方法一：暴力破解法

/* 方法一：暴力破解法：O(mnmin(m,n) ^2)
    找到最大边长就是找到最大面积
    遍历矩阵，遇到1就作为正方形左上角
    根据左上角的坐标计算其最大边长
    从该左上角出发进行遍历，如果都为1则扩大边长
    */
int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        int maxSide=0;// 最大边长
        // 遍历整个矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个1作为正方形的左上角,就更新当前最大边
                    maxSide = max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = min(m-i, n-j);
                    // 遍历
                    for (int k=1; k<currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        bool flag = true;
                        if (matrix[i + k][j + k]=='0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0'||matrix[i + m][j + k]=='0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }

方法二：动态规划法

/* 方法二：动态规划法：
    【状态定义】dp[i][j]表示以(i,j)为右下角所能构成的最大正方形边长
    【状态转移】dp[i][j]的推导需要判断matrix[i][j]的值
    如果matrix[i][j]=='1'，并且i==0||j==0，dp[i][j] = 1;
    如果i!=0||j!=0,那么dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
    【初始状态】
    */
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        int maxSide=0;// 最大边长
        // 遍历整个矩阵
        vector<vector<int>> dp(m,vector<int>(n,0));
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                // 如果当前元素是1
                if (matrix[i][j]=='1') {
                    // 如果是第一行或者第一列，那么 dp[i][j] = 1;
                    if (i==0||j==0) {
                        dp[i][j] = 1;
                    } 
                    else {
                        dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }