什么是动态规划：动态规划中每一个状态一定是由上一个状态推导出来的，然后得出全局最优。如果某一问题有很多重叠子问题，使用动态规划是最有效的。（而贪心没有状态推导，是从局部直接选最优的。）

动态规划五部曲：

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

先考虑自顶向下暴力解法（递归），得出状态转移方程（定义 dp 数组/函数的含义），加入备忘录消除重叠子问题，再将其转化为自顶向上的解法（迭代）。

509. 斐波那契数

  1. //普通动态规划
  2. var fib = function(n) {
  3.     let dp=Array(n+1).fill(0);
  4.     dp[1]=1
  5.     for(let i =2;i<=n;i++){
  6.         dp[i]=dp[i-1]+dp[i-2];
  7.     }
  8.     return dp[n]
  9. };
  10. //优化空间复杂度
  11. var fib = function(n) {
  12.     let p=0,q=1,r;
  13.     if(n<2) return n;
  14.     for(let i =2;i<=n;i++){
  15.         r=p+q;
  16.         p=q;
  17.         q=r;
  18.     }
  19.     return r;
  20. };

70. 爬楼梯

  1. //普通动态规划
  2. // var climbStairs = function(n) {
  3. //     let dp=new Array(n+1).fill(0);
  4. //     dp[0]=1;
  5. //     let choices=[1,2]
  7. //         for(let i = 1;i <= n; i++){ 
  8. //             for(let c of choices){ 
  9. //                 if(i<c) continue;
  10. //                 dp[i]=dp[i]+dp[i-c];
  11. //                 console.log(i,dp[i])
  12. //                 }
  13. //         }
  14. //     return dp[n]
  15. // };
  16. //简单动态规划
  17. // var climbStairs = function(n) {
  18. //     let dp=new Array(n+1).fill(0);
  19. //     dp[1]=1;
  20. //     dp[2]=2;
  21. //     for(let i = 3;i <= n; i++){ 
  22. //         dp[i]=dp[i-1]+dp[i-2];
  23. //     }
  24. //     return dp[n]
  25. // }
  26. //优化空间复杂度,
  27. var climbStairs = function(n) {
  28.     let p = 0, q = 0, r = 1;
  29.     for (let i = 1; i <= n; ++i) {
  30.         p = q;
  31.         q = r;
  32.         r = p + q;
  33.     }
  34.     return r;
  35. };

放苹果

image.png

62. 不同路径

  1. var uniquePaths = function(m, n) {
  2.   let dp=Array(n).fill(1);
  3.   for(let i=1;i<m;i++){
  4.     for(let j=1;j<n;j++){
  5.         //dp[i][j]=dp[i][j-1]+dp[i-1][j]
  6.         dp[j]=dp[j-1]+dp[j] //从二维变成一维
  7.     }
  8.   }
  9.   return dp[n-1]
  10. };

198. 打家劫舍

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function(nums) {
  6.   let dp=Array(nums.length+1).fill(0);
  7.   dp[1]=nums[0];
  8.   for(let i=2;i<nums.length+1;i++){
  9.       dp[i]=Math.max(dp[i-2]+nums[i-1],dp[i-1])
  10.   }
  11.   return Math.max(...dp)
  12. };

213. 打家劫舍 II

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function(nums) {
  6.   const length=nums.length;
  7.   if(length<2) return nums[0];
  8.   return Math.max(dynamic(nums.slice(0,length-1)),dynamic(nums.slice(1,length)))
  9. };
  10. var dynamic =function(nums){
  11.   let pre1=0,pre2=nums[0],cur;
  12.   let result=pre2;
  13.    for(let i=1;i<nums.length;i++){
  14.     cur=Math.max(pre2,pre1+nums[i])
  15.     result=Math.max(result,cur);
  16.     pre1=pre2;
  17.     pre2=cur;
  18.    }
  19.    return result;
  20. }

132. 分割回文串 II

好难啊，脑子绕绕绕
要找到状态转移方程！依赖前一个的结果

  1. var minCut = function(s) {
  2.   const length=s.length;
  3.   let isPalindromic=Array.from(Array(length),()=>Array(length).fill(false))
  4.   for(let i=length-1;i>=0;i--){
  5.       for(let j=i;j<length;j++){
  6.           if(s[i]===s[j]){
  7.             if(j-i<=1){
  8.                isPalindromic[i][j]=true
  9.             }else if(isPalindromic[i+1][j-1]){
  10.                 isPalindromic[i][j]=true;
  11.             }
  12.           }
  13.       }
  14.   }
  15.   let dp=Array(length) //范围是[0, i]的回文子串，最少分割次数是dp[i]。
  16.   for(let i = 0; i < length; i++) dp[i] = i;
  17.   for(let i=1;i<length;i++){
  18.       if(isPalindromic[0][i]){
  19.           dp[i]=0
  20.           continue;
  21.       }
  22.       for(let j =0;j<i;j++){
  23.         if(isPalindromic[j+1][i]){ 
  24.             dp[i]=Math.min(dp[i],dp[j]+1)
  25.         }
  26.       }
  27.   }
  28.   return dp[length-1];
  29. };

背包问题

image.png

0-1背包

每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

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

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

416. 分割等和子集

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var canPartition = function(nums) {
  6.    //两个子集元素相等，所以一个子集的和为总sum/2
  7.    let sum=nums.reduce((pre,cur)=>pre+cur,0);
  8.    if(sum%2!==0) return false;
  9.    let dp=Array(sum/2+1).fill(false);
  10.    dp[0]=true;
  11.    for(let j=0;j<nums.length;j++){
  12.        for(let i=sum/2;i>=1;i--){  //为了防止同一元素用了多次
  13.            if(nums[j]>i) break;
  14.            dp[i]=dp[i] || dp[i-nums[j]] //注意和dp[i]或处理
  15.        }
  16.    }
  17.    return dp[sum/2]
  18. };

474. 一和零

  1. /**
  2.  * @param {string[]} strs
  3.  * @param {number} m
  4.  * @param {number} n
  5.  * @return {number}
  6.  */
  7. var findMaxForm = function(strs, m, n) {
  8.    const dp = Array.from(Array(m+1),()=>Array(n+1).fill(0))
  9.    for(let str of strs){
  10.       let zeros=0,ones=0;
  11.       for (let s of str) {
  12.         s==='0' ? zeros++ :ones++;
  13.       }
  14.       for(let i=m;i>=zeros;i--){
  15.           for(let j=n;j>=ones;j--){
  16.               dp[i][j]=Math.max(dp[i][j],dp[i-zeros][j-ones]+1);
  17.           }
  18.       }
  20.    }
  21.    return dp[m][n];
  22. }

494. 目标和

  1. var findTargetSumWays = function(nums, target) {
  2.     const sum=nums.reduce((pre,n)=>pre+n);
  3.     //s(p)-s(n)=target 
  4.     //s(p)+s(n)+ s(p)-s(n)=sum + target 
  5.     //2 * s(p)= sum + target
  6.     const to=(sum + target)/2;
  7.     if(to < 0 ||  to % 1 !== 0 ) return 0; 
  8.     let dp=new Array(to+1).fill(0);
  9.     dp[0] = 1;
  10.     for(let num of nums){
  11.         for(let i=to;i>=num;i--){ //本质还是01背包问题
  12.             dp[i] += dp[i-num];
  13.         }
  14.     }
  15.     return dp[to];
  16. };

最后一块石头的重量 II

将问题转换为0-1背包，与分割等和子集类似。
难点在于想到0-1背包，因为分成石头总重相近的两块结果最优

  1. var lastStoneWeightII = function (stones) {
  2.     let total = stones.reduce((pre, cur) => pre + cur, 0);
  3.     let target = Math.floor(total / 2);
  4.     let dp = Array(target + 1).fill(0);
  5.     for (let i = 0; i < stones.length; i++) {
  6.         for (let j = target; j >= 0; j--) {
  7.             if (j - stones[i] >= 0) {
  8.                 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
  9.             }
  10.         }
  11.     }
  12.     return total - dp[target] * 2
  13. };

完全背包

每件物品都有无限个（也就是可以放入背包多次）

01背包和完全背包唯一不同就是体现在遍历顺序上

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

279. 完全平方数

  1. //这题遍历顺序不重要，都能得到结果
  2. //以下为先遍历背包，再遍历物品
  3. var numSquares = function(n) {
  4.    let dp=Array(n+1).fill(Infinity);
  5.    dp[0]=0;
  6.    for(let i=1;i<=n;i++){
  7.        for(let j =1;j*j<=n;j++){
  8.            if(j*j>i) break;
  9.            dp[i]=Math.min(dp[i],dp[i-j*j]+1)
  10.        }
  11.    }
  12.    return dp[n]
  13. };

139. 单词拆分

  1. /**
  2.  * @param {string} s
  3.  * @param {string[]} wordDict
  4.  * @return {boolean}
  5.  */
  6. var wordBreak = function(s, wordDict) {
  7.    let dp=new Array(s.length).fill(false);
  8.    dp[0]=true;
  9.    for(let i=1;i<=s.length;i++){
  10.        for(let j=0;j<wordDict.length;j++){
  11.           const length=wordDict[j].length
  12.           if(i<length) continue;
  13.           dp[i]=dp[i-length] && s.substring(i-length,i)===wordDict[j]
  14.           if(dp[i]) break;
  15.        }
  16.    }
  17.    return dp[s.length];
  18. };

排列背包

组合不强调顺序，(1,5)和(5,1)是同一个组合。
排列强调顺序，(1,5)和(5,1)是两个不同的排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
因为如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
如果求最小数，那么两层for循环的先后顺序就无所谓了，因为(1,5)和(5,1)都是2。

518. 零钱兑换 II

这题就是在求组合数。

  1. /**
  2.  * @param {number} amount
  3.  * @param {number[]} coins
  4.  * @return {number}
  5.  */
  6. var change = function(amount, coins) {
  7.    let dp=Array(amount+1).fill(0)
  8.    dp[0]=1;
  9.    for(let i=0;i<coins.length;i++){
  10.        for(let j=1;j<=amount;j++){
  11.           if(coins[i]>j) continue
  12.           dp[j]=dp[j]+dp[j-coins[i]] 
  13.        }
  14.    }
  15.    return dp[amount]
  16. };

377. 组合总和 Ⅳ

这道题提示 顺序不同的序列被视作不同的组合。所以是求排列数

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var combinationSum4 = function(nums, target) {
  7.    let dp=Array(target+1).fill(0);
  8.    dp[0]=1;//注意，可以理解为target为0时也算一种组合个数
  9.    for(let i=1;i<=target;i++){
  10.        for(let j=0;j<nums.length;j++){
  11.            if(nums[j]>i) continue;
  12.            dp[i]=dp[i]+dp[i-nums[j]]
  13.        }
  14.    }
  15.    return dp[target];
  16. };

子序列问题

https://mp.weixin.qq.com/s/zNai1pzXHeB2tQE6AdOXTA

子序列是不连续的。一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。遇到子序列问题，首先想到两种动态规划思路，然后根据实际问题看看哪种思路容易找到状态转移关系。找到状态转移和 base case 之后，一定要观察 DP table，看看怎么遍历才能保证通过已计算出来的结果解决新的问题。
1、第一种思路模板是一个一维的 dp 数组：
在子数组array[0..i]中，以array[i]结尾的目标子序列（最长递增子序列）的长度是dp[i]。

  1. int n = array.length;
  2. int[] dp = new int[n];
  4. for (int i = 1; i < n; i++) {
  5.     for (int j = 0; j < i; j++) {
  6.         dp[i] = 最值(dp[i], dp[j] + ...)
  7.     }
  8. }

2、第二种思路模板是一个二维的 dp 数组：

  1. int n = arr.length;
  2. int[][] dp = new dp[n][n];
  4. for (int i = 0; i < n; i++) {
  5.     for (int j = 1; j < n; j++) {
  6.         if (arr[i] == arr[j]) 
  7.             dp[i][j] = dp[i][j] + ...
  8.         else
  9.             dp[i][j] = 最值(...)
  10.     }
  11. }

本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。
2.1 涉及两个字符串/数组时（比如最长公共子序列）
在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
2.2 只涉及一个字符串/数组时（比如最长回文子序列）
在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]

1143. 最长公共子序列

image.png

  1. var longestCommonSubsequence = function(text1, text2) {
  2.   const n = text1.length, m = text2.length;
  3.   let dp=Array(n+1).fill(0).map(()=> new Array(m+1).fill(0));
  4. //let dp= Array.from(new Array(n+1),() => new Array(m+1).fill(0));
  5.   for(let i =1;i<=n;i++){
  6.     for(let j=1;j<=m;j++){
  7.         if(text1[i-1]===text2[j-1]){
  8.             dp[i][j]=dp[i-1][j-1]+1;
  9.         }else{
  10.             dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])
  11.         }
  12.     }
  13.   }
  14.   return dp[n][m];
  15. };

647. 回文子串

  1. var countSubstrings = function(s) {
  2.   const length=s.length;
  3.   let result=0;
  4.   let dp=Array.from(Array(length),()=>Array(length).fill(false))
  5.   for(let i=length-1;i>=0;i--){
  6.       for(let j=i;j<length;j++){
  7.           if(s[i]===s[j]){
  8.             if(j-i<=1){
  9.                 dp[i][j]=true
  10.                 result++;
  11.             }else if(dp[i+1][j-1]){
  12.                 dp[i][j]=true;
  13.                 result++;
  14.             }
  15.           }
  16.       }
  17.   }
  18.   return result;
  19. }
  21.   //双指针
  22.   var countSubstrings = function(s) {
  23.     const n = s.length;
  24.     var res = 0;
  25.     for (let i = 0; i < 2 * n -1; i++) {
  26.         let L = Math.floor( i/ 2);
  27.         let R = Math.floor(i / 2) + i % 2;
  28.         while(L >= 0 && R < n && s.charAt(L) == s.charAt(R)) {
  29.             L--;
  30.             R++;
  31.             res++
  32.         }
  33.     }
  34.     return res
  35. };

516. 最长回文子序列

与最长回文子串的区别，回文子串也可以用动态规划，但用双指针（从中心向两端扩展）更高效。
1648705381(1).png

  1. var longestPalindromeSubseq = function (s) {
  2.   const length = s.length;
  3.   let dp = Array.from(Array(length), () => Array(length).fill(0));
  4.   for (let i = 0; i < length; i++) {
  5.     dp[i][i] = 1;
  6.   }
  7.   for (let l = length - 1; l >= 0; l--) {
  8.     for (let r = l + 1; r < length; r++) {
  9.       //状态转移方程
  10.       if (s[l] === s[r]) {
  11.         dp[l][r] = dp[l + 1][r - 1] + 2;
  12.       } else {
  13.         dp[l][r] = Math.max(dp[l][r - 1], dp[l + 1][r]);
  14.       }
  15.     }
  16.   }
  17.   return dp[0][length - 1];
  18. };

300. 最长递增子序列

既然是递增子序列，我们只要找到前面那些结尾比 当前3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

  1. function lengthOfLIS(nums: number[]): number {
  2.   const n = nums.length;
  3.   let dp = Array(n).fill(1);
  4.   for (let i = 1; i < n; i++) {
  5.     for (let j = 0; j < i; j++) {
  6.       if (nums[j] < nums[i]) {
  7.         dp[i] = Math.max(dp[i], dp[j] + 1);
  8.       }
  9.     }
  10.   }
  11.   return Math.max(...dp);
  12. }

674. 最长连续递增序列

  1. //easy版最长递增子序列
  2. //先用dp备忘录，然后改成O(1)变量
  3. var findLengthOfLCIS = function(nums) {
  4.   let p=0,q=0,result=0;
  5.   for(let i=0;i<nums.length;i++){
  6.       if(nums[i]>p){
  7.         q=q+1;
  8.         if(q>result)result=q;
  9.       }else{
  10.         q=1;
  11.       }
  12.       p=nums[i]
  13.   }
  14.   return result;
  15. };

72. 编辑距离

详解编辑距离

53. 最大子数组和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

可以使用动态规划，也可以使用贪心算法

动态规划
dp[i]：包括下标i之前的最大连续子序列和为dp[i]，即 i为终点的连续最大子序列和
状态转移公式:
dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和
dp[i] = max(dp[i - 1] + nums[i], nums[i]); 

  2. //动态规划
  3. var maxSubArray = function (nums) {
  4.   const n = nums.length;
  5.   let dp = Array(n).fill(0);
  6.   dp[0] = nums[0];
  7.   for (let i = 1; i < n; i++) {
  8.     dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  9.   }
  10.   return Math.max(...dp);
  11. };

贪心算法

  1. var maxSubArray = function(nums) {
  2.     let ans = nums[0];
  3.     let sum = 0;
  4.     for(const num of nums) {
  5.         if(sum > 0) {
  6.             sum += num;
  7.         } else {
  8.             sum = num;
  9.         }
  10.         ans = Math.max(ans, sum);
  11.     }
  12.     return ans;
  13. };

股票问题

https://mp.weixin.qq.com/s/4nqJMIyCKQD7IJ-HI6S3Vg

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

以这道题分析，之后的所有股票题都在这道基础上改编

  1. var maxProfit = function (k, prices) {
  2.     //dp[天数][至今最大交易数][是否持有]
  3.     //dp[i][j][0]=Math.max(dp[i-1][j][1]+price[i],dp[i-1][j][0])
  4.     //dp[i][j][1]=Math.max(dp[i-1][j-1][0]-price[i],dp[i-1][j][1])
  5.     //初始化dp[-1][...][0] = dp[...][0][0] = 0；dp[-1][...][1] = dp[...][0][1] = -infinity
  6.     //if(k>price.length/2) 则相当于无限次数，调用最佳买卖股票II方法
  7.     const n = prices.length
  8.     if (n <= 0) {
  9.         return 0;
  10.     }
  11.     if (k > prices.length / 2) {
  12.         return maxProfitInfinity(prices)
  13.     }
  14.     let dp = Array.from(Array(n), () => Array.from(Array(k + 1), () => Array(2)));
  15.     for (let i = 0; i < n; i++) {
  16.         dp[i][0][1] = -Infinity;
  17.         dp[i][0][0] = 0;
  18.     }
  19.     for (let i = 0; i < n; i++) {
  20.         for (let j = 1; j <= k; j++) {
  21.             if (i === 0) {
  22.                 dp[i][j][0] = 0;
  23.                 dp[i][j][1] = -prices[i]
  24.                 continue;
  25.             }
  26.             dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0])  //dp[1][1][0]=dp[0][1][1]+2   dp[0][1][0]
  27.             dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1])
  28.         }
  29.     }
  30.     return dp[n - 1][k][0];
  31. };
  32. var maxProfitInfinity = function (prices) {
  33.     const n = prices.length
  34.     if (n <= 0) {
  35.         return 0;
  36.     }
  37.     let dp0, dp1;
  38.     for (let i = 0; i < n; i++) {
  39.         if (i === 0) {
  40.             dp0 = 0;
  41.             dp1 = -prices[i]
  42.             continue;
  43.         }
  44.         dp0 = Math.max(dp1 + prices[i], dp0)  //dp[1][0]=dp[0][1]+4   dp[0][0]
  45.         dp1 = Math.max(dp0 - prices[i], dp1) //dp[1][1]=dp[0][0]-4   dp[0][1]
  46.     }
  47.     return dp0;
  48. };

121. 买卖股票的最佳时机

动态规划

  1. var maxProfit = function (prices) {
  2.     const n = prices.length
  3.     if (n <= 0) {
  4.         return 0;
  5.     }
  6.     let dp = Array.from(Array(n), () => Array(2));
  7.     for (let i = 0; i < n; i++) {
  8.         if (i - 1 < 0) {
  9.             dp[i][1] = -prices[i];
  10.             dp[i][0] = 0;
  11.             continue;
  12.         }
  13.         dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0])
  14.         dp[i][1] = Math.max(- prices[i], dp[i - 1][1])
  15.     }
  16.     return dp[n - 1][0];
  17. };
  18. //空间优化
  19. var maxProfit = function (prices) {
  20.     const n = prices.length
  21.     if (n <= 0) {
  22.         return 0;
  23.     }
  24.     let dp0 = 0, dp1 = -prices[0];
  25.     for (let i = 0; i < n; i++) {
  26.         dp0 = Math.max(dp1 + prices[i], dp0)
  27.         dp1 = Math.max(- prices[i], dp1)
  28.     }
  29.     return dp0;
  30. };

贪心

  1. //局部最优：最高-最低 
  2. let maxProfit = function (prices) {
  3.     let maxSum = 0, minprice = prices[0]
  4.     for (let i = 1; i < prices.length; i++) {
  5.         minprice = Math.min(prices[i], minprice)
  6.         maxSum = Math.max(maxSum, prices[i] - minprice)
  7.     }
  8.     return maxSum
  9. }

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

可以交易无限次

动态规划

  1. //根据买卖股票的最佳时机 ④改编代码，因为k无限所以可以忽略
  2. var maxProfit = function (prices) {
  3.     const n = prices.length
  4.     if (n <= 0) {
  5.         return 0;
  6.     }
  7.     let dp = Array.from(Array(n), () => Array(2));
  8.     for (let i = 0; i < n; i++) {
  9.         if (i === 0) {
  10.             dp[i][0] = 0;
  11.             dp[i][1] = -prices[i]
  12.             continue;
  13.         }
  14.         dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0])  //dp[1][0]=dp[0][1]+4   dp[0][0]
  15.         dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]) //dp[1][1]=dp[0][0]-4   dp[0][1]
  16.     }
  17.     return dp[n - 1][0];
  18. };
  20. //发现每次都是根据前一次得到，空间优化
  21. var maxProfit = function (prices) {
  22.     const n = prices.length
  23.     if (n <= 0) {
  24.         return 0;
  25.     }
  26.     let dp0=0, dp1=-prices[i];
  27.     for (let i = 0; i < n; i++) {
  28.     let temp=dp0;
  29.         dp0 = Math.max(dp1 + prices[i], dp0)  
  30.         dp1 = Math.max(temp - prices[i], dp1) 
  31.     }
  32.     return dp0;
  33. };

贪心

  1. //局部最优：每一次交易都是正收益
  2. var maxProfit = function(prices) {
  3.    let sum=0;
  4.    for(let i=prices.length;i>0;i--){
  5.       const profit=prices[i]-prices[i-1];
  6.       if(profit>0){
  7.          sum+=profit
  8.       }
  9.    }
  10.    return sum;
  11. };

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

无限次，含手续费，即在买卖股票的最佳时机 II的基础上改编。

  1. //在卖出时付手续费
  2. var maxProfit = function (prices, fee) {
  3.     const n = prices.length
  4.     if (n <= 0) {
  5.         return 0;
  6.     }
  7.     let dp0 = 0, dp1 = -prices[0];
  8.     for (let i = 0; i < n; i++) {
  9.         let temp = dp0;
  10.         dp0 = Math.max(dp1 + prices[i] - fee, dp0)//在卖出时付手续费
  11.         dp1 = Math.max(temp - prices[i], dp1)
  12.     }
  13.     return dp0;
  14. };
  15. //在买入时付手续费
  16. var maxProfit = function (prices, fee) {
  17.     const n = prices.length
  18.     if (n <= 0) {
  19.         return 0;
  20.     }
  21.     let dp0 = 0, dp1 = -prices[0] - fee; //若在买入时付，需要注意买入初始值
  22.     for (let i = 0; i < n; i++) {
  23.         let temp = dp0;
  24.         dp0 = Math.max(dp1 + prices[i], dp0)
  25.         dp1 = Math.max(temp - prices[i] - fee, dp1)//在买入时付手续费
  26.     }
  27.     return dp0;
  28. };

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

无限交易次数，但有冷冻期的要求：卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

  1. var maxProfit = function (prices) {
  2.     const n = prices.length
  3.     if (n <= 0) {
  4.         return 0;
  5.     }
  6.     let dp = Array.from(Array(n), () => Array(2));
  7.     for (let i = 0; i < n; i++) {
  8.         if (i - 1 < 0) {
  9.             dp[i][0] = 0;
  10.             dp[i][1] = -prices[i]
  11.             continue;
  12.         }
  13.         if (i - 2 < 0) { //特殊处理i<2的情况
  14.             dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
  15.             dp[i][1] = Math.max(- prices[i], dp[i - 1][1])
  16.             continue; 2
  17.         }
  18.         dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0])
  19.         dp[i][1] = Math.max(dp[i - 2][0] - prices[i], dp[i - 1][1])
  20.     //第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
  22.     }
  23.     return dp[n - 1][0];
  24. };
  25. //优化空间复杂度
  26. var maxProfit = function (prices) {
  27.     const n = prices.length
  28.     if (n <= 0) {
  29.         return 0;
  30.     }
  31.     let dp0 = 0, dp1 = -prices[0];
  32.     let dp_pre = 0;
  33.     for (let i = 0; i < n; i++) {
  34.         let temp = dp0;
  35.         dp0 = Math.max(dp1 + prices[i], dp0)
  36.         dp1 = Math.max(dp_pre - prices[i], dp1)
  37.         dp_pre = temp;
  38.     }
  39.     return dp0;
  40. };

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

能进行两笔交易，即在买卖股票的最佳时机的基础上改编，k=2

  1. var maxProfit = function (prices) {
  2.     const n = prices.length
  3.     if (n <= 0) {
  4.         return 0;
  5.     }
  6.     let dp = Array.from(Array(n), () => Array.from(Array(3), () => Array(2)));
  7.     for (let i = 0; i < n; i++) {
  8.         dp[i][0][1] = -Infinity;
  9.         dp[i][0][0] = 0;
  10.     }
  11.     for (let i = 0; i < n; i++) {
  12.         for (let j = 1; j <= 2; j++) {
  13.             if (i === 0) {
  14.                 dp[i][j][0] = 0;
  15.                 dp[i][j][1] = -prices[i]
  16.                 continue;
  17.             }
  18.             dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0])  //dp[1][1][0]=dp[0][1][1]+2   dp[0][1][0]
  19.             dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1])
  20.         }
  21.     }
  22.     return dp[n - 1][2][0];
  23. };
  24. //因为k不大就1和2的情况，所以可能优化空间复杂度
  25. var maxProfit = function (prices) {
  26.     const n = prices.length
  27.     if (n <= 0) {
  28.         return 0;
  29.     }
  30.     let dpK1H0 = dpK2H0 = 0,
  31.         dpK1H1 = dpK2H1 = -Infinity;
  32.     for (let i = 0; i < n; i++) {
  33.         const price = prices[i]
  34.         dpK1H0 = Math.max(dpK1H1 + price, dpK1H0)
  35.         dpK1H1 = Math.max(- price, dpK1H1)
  36.         dpK2H0 = Math.max(dpK2H1 + price, dpK2H0)
  37.         dpK2H1 = Math.max(dpK1H0 - price, dpK2H1)
  38.     }
  39.     return dpK2H0;
  40. };