动态规划

题目一览图

零、动态规划概述

【动态规划】（Dynamic Programming）一般是求解最值问题，核心是穷举出最值。它和暴力搜索的区别在于求解过程中存在【重叠子问题】，可以用 DP table 来优化穷举过程。

一、有限状态类

类型概述

这种题目所涉及的问题，当前状态都与前有限状态有关，即可以表示dp[i] = fun(dp[i-1],dp[i-2],…)。我们以最简单的斐波那契数列进行说明。

模板题 斐波那契数列

【题目描述**】
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0 , F(1) = 1 , F(N) = F(N-1) + F(N-2) .
【题目分析**】
可以看出第n项只于前两项相关，所以我们可用 DP table 依次记录 F(0) , F(1) , F(2) … F(N) 的结果，每次算dp[i] 只需将 dp[i-1] 和 dp[i-2] 相加即可。
【DP 定义】

• 状态 ： 斐波那契数列第 i 项
• dp[i] ：斐波那契数列第 i 项对应的值。

【Base Case】
因为是与前两项相关，我们需要 dp[0] 和 dp[1] ，对别对应 0 和 1 。
【转移方程】
按照题目要求直接得到转移方程 ： dp[i] = dp[i-1] + dp[i-2]。

var fib = function(n) {
    if( n < 1) return 0;
    if( n === 1 ) return 1;
      // Init DP Table
    const dp = new Array(n+1).fill(0);
      // Base Case
    dp[0] = 0 , dp[1] = 1;
    for( let i = 2 ; i <= n ; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};

【空间压缩**】**
根据题意我们知道第 n 状态只与前两项 dp[n-1] , dp[n-2] 有关，可以进行状态压缩。为了统一命名，我们在本文档统一将前 i 状态命名为 si ，如前一个状态为 s1 。

var fib = function(n) {
    let s1 = 0 , s2 = 1;
    for(let i = 0 ; i < n ; i++ ){
        const tmp = (s1+s2)
        s1 = s2 , s2 = tmp;
    }
    return s1;
};

菲波那切数列代表了与前有限状态的一类题，不过本质上都是有限个状态的转移。

题型一 | 生成数字类

题型串联

1 爬楼梯

【概述】**与**前两个状态相关
【前置题目】**斐波那契数列 - 本质一样，采用爬楼的背景。
【题目描述**】
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。
你有多少种不同的方法可以爬到楼顶呢？
【题目示例**】**

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

【DP 定义】

• 状态 ： 第 i 阶台阶。
• dp[i] ：爬到第 i 阶台阶有 dp[i] 种方式。

【Base Case】
根据题意，我们有两种方式上楼，可得当前状态 dp[x] 只和 dp[x-1] ，dp[x-2] 有关。
考虑到我们数组的起始索引是 0 ，我们把 0 阶台阶作为第一个状态，所以我们只需要初始化 dp[0] 和 dp[1] 即可。

【转移方程】
按照题目要求直接得到转移方程 ： dp[i] = dp[i-1] + dp[i-2]。
【复杂度分析】

• 时间复杂度 O(n)

• 空间复杂度 O(n) -> O(1)

  var climbStairs = function(n) {
  if(n < 2) return n;
  const dp = new Array(n+1).fill(0);
  dp[0] = 1 , dp[1] = 1
  for( let i = 2 ; i <= n ; i++){
     dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n]
  };
  

  【空间压缩**】**
  根据题意我们知道第 n 状态只与前两项 dp[n-1] , dp[n-2] 有关，可以进行状态压缩。为了统一命名，我们在本文档统一将前 i 状态命名为 si ，如前一个状态为 s1 。

  var climbStairs = function(n) {
  if( n < 3 ) return n;
  let s1 = 2 , s2 = 1;
  for( let i = 3 ; i <= n ; i++ ){
     const tmp = s1 + s2;
     s2 = s1 , s1 = tmp;
  }
  return s1;
  };
  

  2 解码方法

  【概述】**与**前两个状态相关，范围的处理
  【前置题目】

• 斐波那契数列 ，爬楼梯 - 背景换到字符串，而且需要进行特殊判断。

【题目描述**】**
一条包含字母 A-Z 的消息通过以下方式进行了编码：

• ‘A’ -> 1
• ‘B’ -> 2
• …
• ‘Z’ -> 26

给定一个只包含数字的非空字符串 s ，请计算解码方法的总数。
【题目示例**】**

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

【DP 定义】

• 状态 ： 字符串 s 0-i 的子串。
• dp[i] ：爬到第 i 阶台阶有 dp[i] 种方式。

【Base Case】
根据题意，我们最长编码长度为 2 ，不同的编码方式会和 dp[x-1] ，dp[x-2] 有关。
考虑到我们数组的起始索引是 0 ，认为空串是第一个子串。
【转移方程】我们的编码方式分为【编码长度为 **1** 】和【编码长度为 **2** 】
具体编码过程有两种基本方式，一个按位讨论，一个是截取整体讨论，前者较为复杂，本题采取后者。

• 【编码长度为 **1** 】说明前一个字符在 0 - 10 之间，说明当前状态可以加上前一个状态方式数，即dp[i] 加上 dp[i-1] 的取值。
• 【编码长度为 **2** 】前两个字符在 9 - 27 之间，说明当前状态可以加上向前第二个状态方式数，即dp[i] 加上 dp[i-2] 的取值。

【复杂度分析】

• 时间复杂度：O(n)

• 空间复杂度：O(n) -> O(1)

  var numDecodings = function(s) {
  if( s[0] === '0' ) return 0;
  const n = s.length;
  const dp = new Array(n+1).fill(0);
  dp[0] = dp[1] = 1;
  for( let i = 2 ; i <= n ; i++ ){
     const one = s.slice(i-1,i) , two = s.slice(i-2,i);
     if( one > 0 && one < 10 ) dp[i] += dp[i-1];
     if( two > 9 && two < 27 ) dp[i] += dp[i-2];
  }
  return dp[n]
  };
  

  【空间压缩**】**
  根据题意我们知道第 n 状态只与前两项 dp[n-1] , dp[n-2] 有关，可以进行状态压缩。为了统一命名，我们在本文档统一将前 i 状态命名为 si ，如前一个状态为 s1 。

  var numDecodings = function(s) {
  if( s[0] === '0' ) return 0;
  const n = s.length;
  let s1 = s2 = 1;
  for( let i = 2 ; i <= n ; i++ ){
     const one = s.slice(i-1,i) , two = s.slice(i-2,i);
     let tmp = 0 ;
     if( one > 0 && one < 10 ) tmp += s1;
     if( two > 9 && two < 27 ) tmp += s2;
     s2 = s1 , s1 = tmp;
  }
  return s1;
  };
  

  **

  题型二 | 连续数组

  题型串联

  1 最大子序和

  【关键词】**连续 跟前一个有关 最大
  【题目描述**】
  给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  【题目示例**】**

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

  【DP 定义】

• 状态 ： 以数组第 i 项为结尾的子数组。

• dp[i] ：以数组第 i 项为结尾的最大子序列之和。

【Base Case】
由于是连续数组，状态取决于前一个有关，所以只初始化第一项即可。dp[0] 表示以第一个数为结尾的子序列之和，即为它本身，所以 dp[0]=nums[0] 。
【转移方程】

• 更新条件是【前一项连续最大和+当前位】>【当前位】，对应 dp[i] = ``Math.max(nums[i],dp[i-1]+nums[i])
• 但需要注意的是 DP Table 存储的是以第 i 项为结尾的最大子序列之和，不是全部的，所谓我们需要额外的变量 res 来记录 最大值。

【复杂度分析】

• 时间复杂度：O(n)
• 空间复杂度：O(n) -> O(1)

  var maxSubArray = function(nums){
  let res = nums[0];
  const dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  for(let i = 1 ; i < nums.length ; i++){
     dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
     res = Math.max(res,dp[i]);
  }
  return res;
  };
  

  【空间压缩**】**
  根据题意我们知道第 i 状态只与前一项 dp[i-1] 有关，可以进行状态压缩。

  var maxSubArray = function(nums){
  let res = pre = nums[0];
  for(let i = 1 ; i < nums.length ; i++){
     pre = Math.max(nums[i],pre+nums[i]);
     res = Math.max(res,pre);
  }
  return res;
  };
  

2 乘积最大子数组

【关键词】**连续 状态转移 最大
【前置题目】**

• 最大子序和 - 加和变成乘积，存在负负得正的情况。

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

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

【题目分析**】
因为存在负负得正的情况，最小值乘以负数有可能成为最大值，所以我们还需要一个 DP Table 存储最小值。当然可以写成一个二维 DP Table，但是为了方便说明，创建了两个 DP Table。
【DP 定义**】

• 状态 ： 以数组第 i 项为结尾的子数组。
• dp[i] ：以数组第 i 项为结尾的最大子序列乘积。

【Base Case】
由于是连续数组，状态取决于前一个有关，所以只初始化第一项即可。dp[0] 表示以第一个数为结尾的子序列之积，即为它本身，所以 dp[0]=nums[0] 。值得注意的是我们需要两个 DP Table ，命名为 dp1 和dp2 ， 分别存储最大乘积和最小乘积。
【转移方程】

• 更新条件是【前一项连续和 * 当前位】>【当前位】。考虑到负负得正的情况，最大连续积可能出现于【前一项连续最大和 * 当前位】和【前一项连续小和 * 当前位】，即 dp1[i] = ``Math.max(nums[i],dp1[i-1]*nums[i],dp2[i-1]*nums[i])。
• 同时我们要更新最小值，dp2[i] = ``Math.min(nums[i],dp1[i-1]*nums[i],dp2[i-1]*nums[i])
• 但需要注意的是 DP Table 存储的是以第 i 项为结尾的最大子序列之积，不是全部的，所谓我们需要额外的变量 res 来记录 最大值。

【复杂度分析】

• 时间复杂度：O(n)

• 空间复杂度：O(n) -> O(1)

  var maxProduct = function(nums) {
  if( !nums.length ) return 0;
  const dp1 = new Array(nums.length).fill(0);
  const dp2 = new Array(nums.length).fill(0);
  let res = nums[0];
  dp1[0] = dp2[0] = nums[0];
  for( let i = 1 ; i < nums.length ; i++){
     dp1[i] = Math.max(dp1[i-1]*nums[i],nums[i],dp2[i-1]*nums[i]);
     dp2[i] = Math.min(dp1[i-1]*nums[i],nums[i],dp2[i-1]*nums[i]);
     res = Math.max(dp1[i],res);
  }
  return res;
  };
  

  【空间压缩**】**
  根据题意我们知道第 i 状态只与前一项 dp[i-1] 有关，可以进行状态压缩。

  var maxProduct = function(nums) {
  if( !nums.length ) return 0;
  let curMin = curMax = res = nums[0];
  for( let i = 1 ; i < nums.length ; i++){
     let tmp = curMax;
     curMax = Math.max(curMax*nums[i],nums[i],curMin*nums[i]);
     curMin = Math.min(tmp*nums[i],nums[i],curMin*nums[i]);
     res = Math.max(res,curMax);
  }
  return res;
  };
  

  3 最长湍流子数组

  【关键词】**连续 状态转移 波浪**
  【题目描述**】
  当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：

• 若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；

• 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。

也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
【题目示例**】**

输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])

【题目分析**】
本题与‘乘积最大子数组’类似，需要两个 DP Table 交互使用，即上升。
【DP 定义**】

• 状态 ： 以数组第 i 项为结尾的子数组。
• dp[i] ：以数组第 i 项为结尾的上升/下降矩阵。

【Base Case】
由于是连续数组，状态取决于前一个有关，所以只初始化第一项即可。dp[0] 表示以第一个数为结尾的子序列之积，即为它本身，所以 dp[0]=nums[0] 。值得注意的是我们需要两个 DP Table ，命名为 dp1 和dp2 ， 分别存储上升数组和下降数组。
【转移方程】存在三种情况【相邻数字增加】、【相邻数字递减】和【相邻数字相同】

• 【相邻数字增加】arr[i-1] < arr[i]
  • 上升 DP Table 增加 ：dp1[i] = dp2[i-1] + 1
  • 下降 DP Table 重置 ：dp2[i] = 1
• 【相邻数字递减】arr[i-1] > arr[i]
  • 下降 DP Table 增加 ：dp2[i] = dp1[i-1] + 1
  • 上升 DP Table 重置 ：dp1[i] = 1
• 【相邻数字相同】arr[i-1] == arr[i] 两个 DP Table 都重置
• 以上三种情况选择最大值作为结果。

【复杂度分析】

• 时间复杂度：O(n)

• 空间复杂度：O(n) -> O(1)

  var maxTurbulenceSize = function(arr) {
  const n = arr.length;
  if(!n) return 0 ;
  const dp1 = new Array(n).fill(0);
  const dp2 = new Array(n).fill(0);
  let res = 1;
  dp1[0] = dp2[0] = 1;
  for( let i = 1 ; i < n ; i++){
     if( arr[i-1] < arr[i] ) dp1[i] = dp2[i-1] + 1;
     else dp1[i] = 1;
  
     if( arr[i-1] > arr[i] ) dp2[i] = dp1[i-1] + 1;
     else dp2[i] = 1;
  
     res = Math.max(dp1[i],dp2[i],res);
  }
  return res;
  };
  

  【空间压缩**】**
  根据题意我们知道第 i 状态只与前一项 dp[i-1] 有关，可以进行状态压缩。两个 DP Table 分别简化成变量 curUp ， curDown 。

  var maxTurbulenceSize = function(arr) {
  const n = arr.length;
  if(!n) return 0 ;
  let curUp  = curDown = res = 1;
  for( let i = 1 ; i < n ; i++){
     let tmpUp , tmpDown;
     if( arr[i-1] < arr[i] ) tmpUp = curDown + 1;
     else tmpUp = 1;
  
     if( arr[i-1] > arr[i] ) tmpDown = curUp + 1;
     else tmpDown = 1;
  
     curUp = tmpUp , curDown = tmpDown;
     res = Math.max(curUp,curDown,res);
  }
  return res;
  };
  

  题型三 | 状态转移

  题型串联

  1 买卖股票的最佳时机

  【关键词】**状态转移
  【题目描述**】
  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
  【题目示例**】**

  输入: [7,1,5,3,6,4]
  输出: 5
  解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
  

  【DP 定义】

• 状态 ： 1. 第 i 天 2. 买卖状态 k = 0 - 卖 ， k = 1 - 买 。

• dp[i][k] ：到第 i 天，选择买/卖，所能得到的最大收益。

【Base Case】

• dp[0][0] 第一天卖出，当然这是不可能的，所以设置 0 。
• dp[0][1] 第一天买入，直接减第一天的价格-prices[0]。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】 ：只能买入一次，每次买入必定是从手头 0 元操作，即 -prices[i]。
• 【卖出】 ：只能卖出一次，且必定发生在买入后，dp[i-1][1] + prices[i]。

• 【无操作】: 取当前值即可。

  var maxProfit = function(prices) {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(()=>new Array(2).fill(0));
  dp[0][0] = 0 , dp[0][1] = -prices[0];
  for( let i = 1 ; i < n ; i++ ){
     dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
     dp[i][1]  = Math.max(dp[i-1][1],-prices[i]);
  }
  return dp[n-1][0];
  };
  

  【空间压缩**】**
  根据题意我们可以将 DP Table 压缩成两个状态，s1 - 卖 s2 - 买。

  var maxProfit = function(prices) {
  const n = prices.length;
  s0 = 0 , s1 = Number.MIN_SAFE_INTEGER;
  for( let i = 0 ; i < n ; i++ ){
     s0 = Math.max(s0,s1 + prices[i]);
     s1 = Math.max(s1,-prices[i]);
  }
  return s0;
  };
  

  2 打家劫舍

  【关键词】**非**连续 有CD
  【题目描述**】
  你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
  给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
  【题目示例**】

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

  【DP 定义】

• 状态 ： 第 i 间房

• dp[i] ：到第 i 间房，偷窃的最高金额。

【Base Case】
由于状态取决于前两个状态有关，所以只初始化第一二项即可。

• dp[0] 到第一间房的最高金额，即直接偷完第一家。
• dp[1] 到第二间房的最高金额，分为【偷第一家，第二家不偷】和【偷第二家】两种情况。

【转移方程】存在两种情况【上一家偷过，本次不可偷】和【本次可以偷】

• 【上一家偷过，本次不可偷】 ：就直接取前一个值 dp[i-1] 。
• 【本次可以偷】 ： 说明前一家没偷 ，dp[i-2]+nums[i]。

• 以上两种情况取最大值。

  var rob = function(nums) {
  if( !nums.length ) return 0;
  const dp = new Array(nums.length).fill(0);
  dp[0] = nums[0], dp[1] = Math.max(nums[0],nums[1]);
  for( let i = 2 ; i < nums.length ; i++){
     dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
  }
  return dp[nums.length-1];
  };
  

  【空间压缩**】**
  根据题意我们知道第 i 状态只与前一项 dp[i-1] 和前第二项 dp[i-2] 有关，可以进行状态压缩。

  var rob = function(nums) {
  if( !nums.length ) return 0;
  if( nums.length < 2) return nums[0];
  s2 = nums[0], s1 = Math.max(nums[0],nums[1]);
  for( let i = 2 ; i < nums.length ; i++){
     const temp = Math.max(s1,s2+nums[i]);
     s2 = s1;
     s1 = temp;
  }
  return s1;
  };
  

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

  【关键词】**状态转移 有CD
  【题目描述**】
  给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
  你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
  【题目示例**】**

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

  【DP 定义】

• 状态 ： 1. 第 i 天 2. 买卖状态 k = 0 - 卖 ， k = 1 - 买 ，k = 2 - 冷冻

• dp[i][k] ：到第 i 天，选择买/卖，所能得到的最大收益。

【Base Case】

• dp[0][0] 第一天卖出，当然这是不可能的，所以设置 0 。
• dp[0][1] 第一天买入，直接减第一天的价格 -prices[0]。
• dp[0][2] 第一天冷却，当然这是不可能的，所以设置 0 。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】 ：发生手中不持股，即 dp[i-1][0]-prices[i] 。
• 【卖出】
  • 进入冷静期 dp[i-1][1] + prices[i]
  • 中间过渡个冷静期 dp[i][0] = dp[i-1][2]。

• 【无操作】: 取当前值即可。

  var maxProfit = function(prices) {
  const n = prices.length;
  if(!n) return 0 ;
  const dp = new Array(n).fill(0).map(()=>new Array(3).fill(0));
  dp[0][0] = dp[0][2] = 0 , dp[0][1] = -prices[0] ;
  for( let i = 1 ; i < n ; i++){
     dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
     dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
     dp[i][2] = dp[i-1][1] + prices[i];
  }
  return Math.max(dp[n - 1][0], dp[n - 1][2]);
  };
  

  【空间压缩**】**
  根据题意我们可以将 DP Table 压缩成两个状态，s0 - 卖 s1 - 买 s_cold - 冷冻。

  var maxProfit = function(prices) {
  const n = prices.length;
  if(!n) return 0 ;
  let s0 = 0 , s1 = Number.MIN_SAFE_INTEGER, s_cold = 0;
  for( let i = 0 ; i < n ; i++){
     const tmp = s0;
     s0 = Math.max(s0,s1+prices[i]);
     s1 = Math.max(s1,s_cold-prices[i]);
     s_cold = tmp;
  }
  return s0;
  };
  

  4 买卖股票的最佳时机 II

  【关键词】**状态转移 无限次
  【题目描述**】
  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
  【题目示例**】**

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

  【DP 定义】

• 状态 ： 1. 第 i 天 2. 买卖状态 k = 0 - 卖 ， k = 1 - 买

• dp[i][k] ：到第 i 天，选择买/卖，所能得到的最大收益。

【Base Case】

• dp[0][0] 第一天卖出，当然这是不可能的，所以设置 0 。
• dp[0][1] 第一天买入，直接减第一天的价格 -prices[0]。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】 ：发生手中不持股，即 dp[i-1][0]-prices[i] 。
• 【卖出】 ：卖掉手中的股份， dp[i-1][1] + prices[i]。

• 【无操作】: 取当前值即可

  var maxProfit = function(prices) {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(()=>new Array(2).fill(0));
  dp[0][0] = 0 , dp[0][1] = -prices[0];
  for( let i = 1 ; i < n ; i++){
     dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
     dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
  }
  return dp[n-1][0];
  };
  

  【空间压缩**】**
  根据题意我们可以将 DP Table 压缩成两个状态，s0 - 卖 s1 - 买。

  var maxProfit = function(prices) {
  const n = prices.length;
  let s0 = 0 , s1 = Number.MIN_SAFE_INTEGER;
  for( let i = 0 ; i < n ; i++){
     s0 = Math.max(s0,s1+prices[i]);
     s1 = Math.max(s1,s0-prices[i]);
  }
  return s0;
  };
  

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

  【关键词】**状态转移 无限次 + 手续费
  【题目描述**】
  给定一个整数数组 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.
  

  【DP 定义】

• 状态 ： 1. 第 i 天 2. 买卖状态 k = 0 - 卖 ， k = 1 - 买

• dp[i][k] ：到第 i 天，选择买/卖，所能得到的最大收益。

【Base Case】

• dp[0][0] 第一天卖出，当然这是不可能的，所以设置 0 。
• dp[0][1] 第一天买入，直接减第一天的价格 -prices[0]。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】 ：发生手中不持股，即 dp[i-1][0]-prices[i] 。
• 【卖出】 ：卖掉手中的股份， dp[i-1][1] + prices[i]。

• 【无操作】: 取当前值即可

  var maxProfit = function(prices, fee) {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(()=>new Array(2).fill(0));
  dp[0][0] = 0 , dp[0][1] = -prices[0];
  for( let i = 1 ; i < n ; i++){
     dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
     dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
  }
  return dp[n-1][0];
  };
  

  【空间压缩**】**
  根据题意我们可以将 DP Table 压缩成两个状态，s0 - 卖 s1 - 买。

  var maxProfit = function(prices, fee) {
  const n = prices.length;
  let s0 = 0 , s1 = Number.MIN_SAFE_INTEGER;
  for( let i = 0 ; i < n ; i++){
     s0 = Math.max(s0,s1+prices[i]);
     s1 = Math.max(s1,s0-prices[i]-fee);
  }
  return s0;
  };
  

  6 买卖股票的最佳时机 III

  【关键词】**状态转移 2次交易
  【题目描述**】
  给定一个数组，它的第 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 。
  

  【DP 定义】

• 状态 ： 1. 第 i 天 2. 买卖状态 k = 0 - 1次卖 ， k = 1 - 1次买 ，k = 2 - 2次卖 ， k = 3 - 2次买 。

• dp[i][k] ：到第 i 天，选择买/卖，所能得到的最大收益。

【Base Case】

• dp[0][0] 初始状态，设置为 0 。
• dp[0][2] 第一、二天手上有股份，当然这是不可能的，所以设置 0 。
• dp[0][1]，dp[0][3] 第一、二天手上无股份，直接减第一天的价格 -prices[0]。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】
  • 第一次买入dp[i][1]，从 k=0 状态购入股票，dp[i - 1][0] - prices[i] 。
  • 第二次买入dp[i][3]，从 k=2 状态购入股票，dp[i - 1][2] - prices[i] 。
• 【卖出】
  • 第一次卖出dp[i][2]，从 k=1 状态卖出股票，dp[i - 1][1] + prices[i] 。
  • 第二次卖出dp[i][4]，从 k=3 状态卖出股票，dp[i - 1][3] + prices[i] 。

• 【无操作】: 保持当前值。

  var maxProfit = function(prices) {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(()=>new Array(5).fill(0));
  dp[0][0] = 0 , dp[0][1] = -prices[0] , dp[0][3] = -prices[0];
  for( let i = 1 ; i < n ; i++ ){
     dp[i][0] = dp[i-1][0] ;
     dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
     dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
     dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
     dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
  }
  return dp[n-1][4];
  };
  

  【空间压缩**】**
  根据题意我们可以将 DP Table 压缩成两个状态，sx0 - 第x次卖 sx1 - 第x次买。

  var maxProfit = function(prices) {
  const n = prices.length;
  let s20 = s01 = s10 = s11 = Number.MIN_SAFE_INTEGER;
  for( let i = 0 ; i < n ; i++){
     s01 = Math.max(s01,-prices[i]);
     s10 = Math.max(s10,s01+prices[i]);
     s11 = Math.max(s11,s10-prices[i]);
     s20 = Math.max(s20,s11+prices[i]);
  }
  return Math.max(s10,s20);
  }
  

  7 买卖股票的最佳时机 IV

  【关键词】**状态转移 k次交易
  【题目描述**】
  给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
  设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
  【题目示例**】**

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

  【题目分析】
  本题其实就是 2 次拓展成未定次，加个 for 循环即可。但这也意味着时间复杂度上升，所以要做适当优化。
  第一个优化是，当 k>n/2 时可以等效为无穷次交易，因为买卖各一次，最多占一半。
  第二个优化是，当加入第几次购买这个维度时， DP Table 达到三维，空间复杂度也比较高，结合之前的空间优化，可以将第i天那个维度进行优化，故后文直接给出压缩后版本。
  【DP 定义】

• 状态 ： 1. 第 i 天（优化掉） 2. 买卖状态 k 3. 买卖次数 count

• dp[i][count][k] ：到第 i 天，第count次买/卖，所能得到的最大收益。

【Base Case】

• dp[0][count][0] 表示未持股的状态，设置为 0 。
• dp[0][count][1] 表示持股的状态，不过第几次都直接减第一天的价格 -prices[0]。

【转移方程】存在三种选择【买入】【卖出】和【无操作】

• 【买入】第count次买入dp[i][count][1]，从上一个状态购入股票，dp[i - 1][count-1][0] - prices[i] 。
• 【卖出】 第count次买入dp[i][count][1]，从上一个状态卖出股票，dp[i - 1][count-1][0] + prices[i] 。

• 【无操作】: 保持当前值。

  const maxProfitUnlimit = (prices)=>{
  const n = prices.length ;
  let s0 = 0 , s1 = Number.MIN_SAFE_INTEGER;
  for( let i = 0 ; i < n ; i++){
     s0 = Math.max(s0,s1+prices[i]);
     s1 = Math.max(s1,s0-prices[i]);
  }
  return s0;
  }
  var maxProfit = function(k, prices) {
  const n = prices.length ; 
  if( n === 0 ) return 0;
  if( k > n/2 ) return maxProfitUnlimit(prices);
  const dp = new Array(k+1).fill(0).map(()=>new Array(2).fill(0));
  for( let i = 0 ; i < n ; i++){
     for( let j = k ; j > 0 ; j--){
         if( !i ) {
             dp[j][0] = 0 , dp[j][1] = -prices[i];
             continue;
         }
         dp[j][0] = Math.max(dp[j][0],dp[j][1]+prices[i]);
         dp[j][1] = Math.max(dp[j][1],dp[j-1][0]-prices[i]);
     }
  }
  return dp[k][0];
  };
  

  题型四 | 二维矩阵

  题型串联

  1 不同路径

  【关键词】**二维
  【题目描述**】
  一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
  问总共有多少条不同的路径？
  【题目示例**】**

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

  【DP 定义】

• 状态 ： 矩阵位置 (i, j)

• dp[i][j] ：到达位置 (i, j) 的格子，一共有 dp[i][j] 种方式。

【Base Case】

• dp[0][…] 表示一直向右走，方式都是 1 。
• dp[…][0] 表示一直向左走，方式都是 1 。
  

【转移方程】
当前值就是上方和左方的路径数之和，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

var uniquePaths = function(m, n) {
    const dp = new Array(n).fill(1).map(()=>new Array(m).fill(1));

    for( let i = 1 ; i < n ; i++ ){
        for( let j = 1 ; j < m ; j++ ){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[n-1][m-1];
};

【空间压缩**】**
根据题意我们知道第 i，j 状态只与上方向 dp[i-1][j] 和左方向 dp[i][j-1] 有关，可以进行状态压缩。

var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(1);

    for( let i = 1 ; i < n ; i++ ){
        for( let j = 1 ; j < m ; j++){
            dp[j]=dp[j-1]+dp[j];
        }
    }
    return dp[m-1];
};

2 不同路径 II

【关键词】**二维
【题目描述**】
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
【题目示例**】**

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

【DP 定义】

• 状态 ： 矩阵位置 (i, j)
• dp[i][j] ：到达位置 (i, j) 的格子，一共有 dp[i][j] 种方式。

【Base Case】

• dp[0][…] 表示一直向右走，遇到障碍后都是不可达到，即路径数为 0 。
• dp[…][0] 表示一直向左走，遇到障碍后都是不可达到，即路径数为 0 。
  

【转移方程】
当前值就是在无障碍的时候，上方和左方的路径数之和，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length , n = obstacleGrid[0].length;
    const dp = new Array(m).fill(0).map(()=>new Array(n).fill(0));
    for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
    for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
};

【空间压缩**】**
根据题意我们知道第 i，j 状态只与上方向 dp[i-1][j] 和左方向 dp[i][j-1] 有关，可以进行状态压缩。

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length , n = obstacleGrid[0].length;

    const dp = new Array(n).fill(0);
    dp[0] = obstacleGrid[0][0]? 0 : 1;

    for( let i = 0 ; i < m ; i++){
        for( let j = 0 ; j < n ; j++){
            if(obstacleGrid[i][j]===1) dp[j]=0;
            else if(j) dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
};

3 最小路径和

【关键词】**二维 权重
【题目描述**】
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
【题目示例**】**

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

【DP 定义】

• 状态 ： 矩阵位置 (i, j)
• dp[i][j] ：到达位置 (i, j) 的格子，权重总和为 dp[i][j] 。

【Base Case】

• dp[0][…] 表示一直向右走，权重单方向累加 。
• dp[…][0] 表示一直向左走，权重单方向累加 。

【转移方程】
当前值是上方和左方的总权重的最大值加上当前值，即 dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j]。

var minPathSum = function(grid) {
    const m = grid.length , n = grid[0].length;
    const dp = new Array(m).fill(0).map(()=>new Array(n).fill(0));
    for( let i = 0 ; i < m ; i++ ){
        dp[i][0] = i ? dp[i-1][0] + grid[i][0] : grid[i][0];
        for( let j = 1 ; j < n ; j++){
            dp[i][j] = i ? Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j] : dp[i][j-1] + grid[i][j];
        }
    }
    return dp[m-1][n-1]
};

【空间压缩**】**
根据题意我们知道第 i，j 状态只与上方向 dp[i-1][j] 和左方向 dp[i][j-1] 有关，可以进行状态压缩。

var minPathSum = function(grid) {
    const m = grid.length , n = grid[0].length;

    const dp = new Array(n).fill(0);

    for( let i = 0 ; i < m ; i++ ){
        dp[0] = dp[0] + grid[i][0];
        for( let j = 1 ; j < n ; j++){
            if( !i ) dp[j] = dp[j-1] + grid[i][j];
            else dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
        }
    }
    return dp[n-1];
};

4 地下城游戏

【关键词】**二维 逆向
【题目描述**】
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
【题目示例**】**

[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

【分析】
如果按照传统的正向推 DP 的话，我们有两个需要考虑两个因素：初始值最小（核心）和路径和最大（为了可以活下去）。由于两者同样重要导致这样的动态规划是不满足「无后效性」的。
如果从后往前推 DP 的话，就可以少考虑路径和最大这一因素，减少一个条件。
【DP 定义】

• 状态 ： 矩阵位置 (i, j)
• dp[i][j] ：骑士能到达位置 (i, j) 的格子的最小初始血量 dp[i][j] 。
  

【Base Case】
首先初始化起始点，因为我们要计算最低初始血量，所以出发点 dp[n-1][m-1] 有两种基本情况：

• 【房间是回血的魔法球】骑士保持最低血量 1 到达该点即可。
• 【房间是恶魔守卫或者空】骑士保持需要最低血量 1 加上扣血量 dungeon[m-1][n-1]。

然后是 dp[0][…] 和 dp[…][0] ，因为是单方向的，与其他节点不同需要特殊赋值。
【转移方程】存在两种情况【房间是回血的魔法球】和【房间是恶魔守卫或者空】

• 首先，不管哪种情况，血量都不能小于 1 。
• 【从上方走来】dp[i][j] = Math.min(dp[i+1][j],dp[i][j])

• 【从左方走来】dp[i][j] = Math.min(dp[i][j],dp[i][j+1])

  var calculateMinimumHP = function(dungeon) {
  const m = dungeon.length , n = dungeon[0].length;
  const dp = new Array(m).fill(0).map(()=>new Array(n).fill(Number.MAX_SAFE_INTEGER));
  dp[m-1][n-1] = dungeon[m-1][n-1] > 0 ? 1 : 1 - dungeon[m-1][n-1];
  for( let i = m-1 ; i >= 0 ; i-- ){
     for( let j = n-1 ; j>=0 ; j-- ){
         if( i === m-1 && j === n-1) continue;
         if( i !== m - 1 ) dp[i][j] = Math.min(dp[i+1][j],dp[i][j]);
         if( j !== n - 1 ) dp[i][j] = Math.min(dp[i][j],dp[i][j+1]);
         dp[i][j] = Math.max(1,dp[i][j]-dungeon[i][j]);
     }
  } 
  return dp[0][0];
  };
  

  【空间压缩**】**
  因为只跟上和左有关，所以可以进行空间压缩。为了化简初始条件，给 DP Table 多加一行。

  var calculateMinimumHP = function(dungeon) {
  const m = dungeon.length , n = dungeon[0].length;
  const dp = new Array(n+1).fill(Number.MAX_SAFE_INTEGER);
  
  dp[n-1] = dungeon[m-1][n-1]>0?1:1-dungeon[m-1][n-1];
  
  for(let i = m-1 ; i>=0 ; i--){
     for(let j = n-1 ; j>=0 ; j--){
         if(i == m-1 && j == n - 1) continue;
         dp[j] = Math.max(1,Math.min(dp[j],dp[j+1])-dungeon[i][j]);
  
     }
  }
  return dp[0];
  };
  

  5 摘樱桃

  【关键词】**二维 逆向
  【题目描述**】
  一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：

• 0 表示这个格子是空的，所以你可以穿过它。

• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
• -1 表示这个格子里有荆棘，挡着你的路。

你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

• 从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
• 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
• 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

【题目示例**】**

输入: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
输出: 5
解释： 
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。

【分析】
这道题需要从正反走两次取到最多樱桃，不如将问题转换为从左上选 两条路线 到达右下角，所以此时需要多考虑一个最多樱桃的路径。
为了简化问题，我们假设我们走了 t 步之后，两个路径点分别是(r1 , c1)和(r2 , c2)。直观的讲，我们可以将 DP Table 设置为 dp[r1][c1][r2][c2] , 当然这个复杂度过高，可以通过等式关系 r1+c1 = r2+c2 = t，化简掉一个参数，变成 dp[r1][c1][c2] 。此时 DP Table 存储的是从(r1 , c1) 和 (r2 , c2)两点到达 (N-1,N-1)的最多樱桃数。
【DP 定义】

• 状态 ： 矩阵位置 (r1, c1) 和 (r1+r2-c2, c2)
• dp[i][j] ：到达位置为 (r1, c1)和 (r1+r2-c2, c2) 的格子的最多樱桃数 dp[r1][c1][c2] 。

【Base Case】
为了方便初始化，在最左和右加一个空白列（-1），然后具体遍历从 1 开始 。
【转移方程】
首先考虑不计算的情况

• r2 不合法的时候
• (r1 , c1)和 (r2 , c2) 相同 或者 遇到障碍的情况。

然后需要从四个方向更新 DP Table，由于存在两个点会涉及相同点的情况，需要先用一个变量将结果存储。

• ( r1-1 , c1 ) 和 ( r2 , c2-1 ) — dp[r1-1][c1][c2-1]
• ( r1-1 , c1 ) 和 ( r2-1 , c2 ) — dp[r1-1][c1][c2]
• ( r1 , c1-1 ) 和 ( r2 , c2-1 ) — dp[r1][c1-1][c2-1]
• ( r1 , c1-1) 和 ( r2-1 , c2 ) — dp[r1][c1][c2-1]

var cherryPickup = function(grid) {
    const n = grid.length;
    const dp = new Array(n+1).fill(0)
        .map(()=>new Array(n+1).fill(0)
            .map(()=>new Array(n+1).fill(-1)));
    dp[1][1][1] = grid[0][0];

    for( let r1 = 1 ; r1 <= n ; r1++){
        for( let c1 = 1 ; c1 <= n ; c1++){
            for( let c2 = 1 ; c2 <= Math.min(r1+c1,n); c2++){
                const r2 = r1+c1-c2;
                if( r2 > n || r2 < 1 ) continue;
                if( grid[r1-1][c1-1] === -1 || grid[r2-1][c2-1] === -1 ) continue;
                let tmp = Math.max( dp[r1-1][c1][c2-1] , dp[r1-1][c1][c2] , dp[r1][c1-1][c2-1] , dp[r1][c1-1][c2] );
                if( tmp < 0 ) continue;
                tmp = tmp + grid[r1-1][c1-1] + ((r1 === r2 && c1 === c2 )? 0 : grid[r2-1][c2-1]);
                dp[r1][c1][c2] = tmp;
            }
        }
    }

    return dp[n][n][n] < 0 ? 0 : dp[n][n][n];
};

二、字符串类

类型概述

对于两个字符串/数组（ s1 和 s2 ）的动态规划问题，DP table 常采用如下构造：

其中，dp[i][j]表示对于 s1 [1…i] 和 s2 [1…j] 的目标值。以上图为例子，dp[2][1] 表示对于 ‘HE’和‘H’的目标值。
Base Case。从上图可以看出，我们专门让0索引设置为空，dp[0][…] 和 dp[…][0] 分别表示当一串为空的时候，目标值应该为多少。不难理解，这就是我们的 Base case ，作为矩阵的初始条件。
转移方程。该类问题的转移方程一般来自三个方向：

• dp[i-1][j-1] ：i 和 j 方向同时增加一个字母，对目标值的影响。此方向相当于增加两个字符，一般用于条件 s1[i] === s2[j] 时的特殊操作。
• dp[i][j-1] ：j 方向同时增加一个字母，对目标值的影响。
• dp[i-1][j] ：i 方向同时增加一个字母，对目标值的影响。 ```javascript const m = s1.length , n = s2.length ; const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));

for( let i = 0 ; i <= m ; i++ ){ for( let j = 0 ; j <= n ; j++ ){ if( !(i * j) ) { // base case }; else if ( s1[i-1] === s2[j-1] ) { dp[i][j] = fun1(dp[i-1][j-1]) }
else { dp[i][j] = fun2(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) } } }

return dp[m][n]

<a name="t7R1C"></a>
### 题型一 | 共同子结构
<a name="1bUwp"></a>
#### 题型串联
<a name="S0llv"></a>
#### 1 [最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)
**【关键词】****子串（连续） 最长**<br />**【题目描述****】**<br />给两个整数数组  A  和  B ，返回两个数组中公共的、长度最长的子数组的长度。<br />**【题目示例****】**

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

**【DP 定义】**<br />dp[i][j] - 对于数组 `A [ 0 : i ]` 和 数组 `B [ 0 : j ]` 最长重复子数组的长度。<br />【**Base Case**】<br />**dp[0][...] 和 dp[...][0]** 都有一串为空，所以初始化为 0。<br />【**转移方程**】

   - **s1[i] !== s2[j] : **说明此时子串不连续，dp直接设置为0。
   - **s1[i] === s2[j] : **说明此时子串长度可以增加，即 dp[i-1][j-1] +1。
   - **综上，dp[i][j] = A[i-1] === B[j-1] ? dp[i-1][j-1] + 1 : 0**

【**复杂度分析**】

   - **时间复杂度**：O(mn)
   - **空间复杂度**：O(mn)
```javascript
var findLength = function(A, B) {
    const m = A.length , n = B.length;
    const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
    let res = 0;
    for( let i = 1 ; i <= m ; i++ ){
        for( let j = 1 ; j <= n ; j++ ){
            dp[i][j] = A[i-1] === B[j-1] ? dp[i-1][j-1] + 1 : 0;
            res = Math.max(dp[i][j],res);
        }
    }
    return res;
};

【空间压缩**】**
由转移方程可知，dp[i][j] 只与一个方向的前置变量（ dp[i-1][j-1] ）有关，所以可以进行空间压缩。

var findLength = function(A, B) {
    const m = A.length , n = B.length;
    const dp = new Array(m+1).fill(0);
    let res = 0 ;
    for( let i = 1 ; i <= m ; i++ ){
        for( let j = n ; j >= 1 ; j-- ){
            dp[j] = A[i-1] === B[j-1] ? dp[j-1] + 1 : 0;
            res = Math.max(dp[j],res);
        }
    }
    return res;
};

2 最长公共子序列

【关键词】**子序列（非连续 有序）最长
【题目描述**】
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
【题目示例**】**

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

【Base Case】
dp[0][…] 和 dp[…][0] 都有一串为空，注定子数组长度为 0，故初始化为 0。
【转移方程】

• s1[i] !== s2[j]
  • 说明s1[i]， s2[j]有一个不在最长公共子序列中
  • 所以取 dp[i][j-1] 和 dp[i-1][j] 的最大值
• s1[i] === s2[j] : 说明此时子序列长度可以增加，即 dp[i-1][j-1] +1。
• 综上，**dp[i][j] = s1[i-1] === s2[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j],dp[i][j-1])**

  var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length , n = text2.length;
  const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
  for( let i = 1 ; i <= m ; i++){
     for( let j = 1 ; j <= n ; j++){
         dp[i][j] = text1[i-1] === text2[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j],dp[i][j-1]);
     }
  }
  return dp[m][n]
  };
  

  3 不相交的线

  【关键词】**子序列（非连续 有序）最长
  【题目描述**】
  我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
  现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
  以这种方法绘制线条，并返回我们可以绘制的最大连线数。
  【题目示例**】**

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

【解题思路】
本题与最长公共子序列一直，都是有顺序相似子序列

var maxUncrossedLines = function(A, B) {
    const m = A.length , n = B.length;
    const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));

    for( let i = 1 ; i <= m ; i++){
        for( let j = 1 ; j <= n ; j++){
            dp[i][j] = A[i-1] === B[j-1] ? dp[i-1][j-1]+ 1 : Math.max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[m][n];
};

题型二 | 匹配字符串

题型串联

1 通配符匹配

【关键词】* 的特殊处理
【题目描述**】
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘‘ 的通配符匹配。
【题目示例**】*

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

【Base Case】
对于dp[0][…] 和 dp[…][0]来说，只要在两个串都为空的时候才是正确，其他都是不匹配。
【转移方程】

• 主要是对 * 的讨论：
  • • 是匹配任意字符串，与上一题有所区分。
  • 这题不想上题一样，*需要和字符搭配，所以更为简单，只需要判断 dp[i][j-1] 和 dp[i-1][j]

• 一般情况只用考虑等式 p[j] === ‘?’ || p[j] === s[i] 即可。

  var isMatch = function(s, p) {
  const m = s.length , n = p.length;
  s = ' ' + s , p = ' ' + p;
  
  const dp = new Array(m+1).fill(false).map(()=>new Array(n+1).fill(false));
  
  dp[0][0] = true;
  for( let i = 0 ; i <= m ; i++ ){
     for( let j = 1 ; j <= n ; j++){
         if( p[j] === '*'){
             dp[i][j] = dp[i][j-1] || i && dp[i-1][j];
         }else{
             dp[i][j]= i && dp[i-1][j-1] && (s[i]===p[j]||p[j]==='?');
         }
     }
  }
  return dp[m][n]
  };
  

  2 正则表达式匹配
  

  【关键词】* 的特殊处理
  【题目描述**】
  给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘‘ 的正则表达式匹配。
  【题目示例**】*

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

  【Base Case】
  对于dp[0][…] 和 dp[…][0]来说，只要在两个串都为空的时候才是正确，其他都是不匹配。
  【转移方程】

• 主要是对 * 的讨论：

  • * 是匹配零个或者多个问题
  • Step I : 判断当前字符后一个是否为 * ，如果是，跳过当前字符。
  • Step II : 判断当前字符是否为 * ，分以下一种匹配情况，
    • _* 匹配空，即dp[i][j-2]就是正确的，当前肯定也正确的。
    • *匹配一堆，
      • 一个_ ，dp[i-1][j-2] && p[j-1]===’.’ || p[j-1] === s[i]
      • 两个_ ，dp[i-2][j-2] && p[j-1]===’.’ || p[j-1] === s[i] && p[j-2]===’.’ || p[j-2] === s[i-1]
      • 可以发现，能够改写为 i && dp[i-1][j] && ( p[j-1]===’.’ || p[j-1] === s[i] )

• 一般情况只用考虑等式 p[j] === ‘.’ || p[j] === s[i] 即可。

  var isMatch = function(s, p) {
  const m = s.length , n = p.length;
  s = ' ' + s , p = ' ' + p;
  const dp = new Array(m+1).fill(false).map(()=>new Array(n+1).fill(false));
  dp[0][0] = true;
  
  for(let i = 0 ; i <= m ; i++){
     for( let j = 1 ; j <= n ; j++ ){
         if( j < n && p[j+1] === '*') continue;
         if( i && p[j] !== '*' ) dp[i][j] = dp[i-1][j-1] && ( p[j] === '.' || p[j] === s[i] );
         else if( p[j] === '*' ) dp[i][j] = dp[i][j-2] || ( i && dp[i-1][j] && ( p[j-1]==='.' || p[j-1] === s[i] ));
     }
  }
  return dp[m][n];
  };
  

  题型三 | 字符串转化

  题型串联

  1 两个字符串的删除操作

  【关键词】**删除
  【题目描述**】
  给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
  【题目示例**】**

  [1,2,3,4,5]
  输出：此列表中的结点 3 (序列化形式：[3,4,5])
  

  【Base Case】
  dp[0][…] 和 dp[…][0] 说明有一串为空，要想实现转变，需要将另一串全部删除，所以此时是dp[i][j]=i+j。
  【转移方程】

• s1[i] !== s2[j] :

  • 说明新增的字符需要被删除，即在上一次选择上加 1 。
  • 上一次选择选 dp[i][j-1] 和 dp[i-1][j] 的最小值。
• s1[i] === s2[j]
  • 说明新增字符不用被删除，直接等于 dp[i-1][j-1] 即可。

    var minDistance = function(s1, s2) {
    const m = s1.length , n = s2.length;
    const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
    for( let i = 0 ; i <= m ; i++){
    for( let j = 0 ; j <= n ; j++ ){
        if( !(i*j) ) dp[i][j] = i+j;
        else dp[i][j] = s1[i-1] === s2[j-1] ? dp[i-1][j-1] : Math.min(dp[i-1][j],dp[i][j-1])+1;
    }
    }
    return dp[m][n];
    };
    

    【其他方案】
    可以看出两个串删到最后就是两者最长公共子序列，所以可以采取此方法得到答案。

    var minDistance = function(word1, word2) {
    const m = word1.length , n = word2.length;
    const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
    for( let i = 1 ; i <= m ; i++){
    for( let j = 1 ; j <= n ; j++ ){
        dp[i][j] = word1[i-1] === word2[j-1] ? dp[i][j] = dp[i-1][j-1]+1 :  Math.max(dp[i-1][j],dp[i][j-1]);
    }
    }
    return m+n-2*dp[m][n];
    };
    

    2 两个字符串的最小ASCII删除和

    【关键词】**删除
    【题目描述**】
    给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
    【题目示例**】**

    输入: "sea", "eat"
    输出: 2
    解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
    

【Base Case】

• dp[0][…] 说明 s2 删除成空串，即记录全部的ASCII值，dp[0][j] = dp[0][j-1] + s1[i-1].charCodeAt()。
• dp[…][0] 说明 s1 删除成空串，即记录全部的ASCII值, dp[i][0] = dp[i-1][0] + s2[j-1].charCodeAt()。

【转移方程】

• s1[i] !== s2[j] :
  • 说明新增的字符需要被删除，即在上一次选择上加当前字符ASCII 。
  • 上一次选择选 dp[i][j-1] 和 dp[i-1][j] 的最小值。

• s1[i] === s2[j]

  • 说明新增字符不用被删除，直接等于 dp[i-1][j-1] 即可。

    var minimumDeleteSum = function(s1, s2) {
    const m = s1.length , n = s2.length;
    const dp = new Array(m+1).fill(0).map(()=>new  Array(n+1).fill(0));
    for( let i = 1 ; i <= m ; i++ ) dp[i][0] = dp[i-1][0] + s1[i-1].charCodeAt();
    for( let j = 1 ; j <= n ; j++ ) dp[0][j] = dp[0][j-1] + s2[j-1].charCodeAt();
    for( let i = 1 ; i <= m ; i++){
    for( let j = 1 ; j <=n ; j++){
        if( s1[i-1] === s2[j-1] ) dp[i][j] = dp[i-1][j-1];
        else dp[i][j] = Math.min(dp[i-1][j]+s1[i-1].charCodeAt(),dp[i][j-1]+s2[j-1].charCodeAt())
    }
    }
    return dp[m][n];
    };
    

    3 编辑距离

    【关键词】**替换 增加 **删除
    【题目描述**】
    给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
    【题目示例**】

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

    【Base Case】

• dp[0][…] 说明 word2 要转换为空串，即全部删除，dp[0][j] = j。

• dp[…][0] 说明 空串 要转换为word1，即全部添加, dp[i][0] = i。

【转移方程】

• s1[i] !== s2[j] :
  • 新增 dp[i-1][j] + 1。
  • 删除 dp[i][j-1] + 1;
  • 替换 dp[i-1][j-1] + 1;
• s1[i] === s2[j]
  • 说明新增字符不用被编辑，直接等于 dp[i-1][j-1] 即可

    var minDistance = function(word1, word2) {
    const m = word1.length , n = word2.length;
    if( m * n === 0 ) return m+n;
    const dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
    for( let i = 0 ; i <=m ; i++){
    for( let j = 0 ; j <=n ; j++){
        if(!(i*j)) dp[i][j] = i+j 
        else dp[i][j] = word1[i-1] === word2[j-1]? dp[i-1][j-1] :  Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1;
    }
    }
    return dp[m][n];
    };
    

    三、背包问题

    类型概述

    背包问题分为 0-1 背包和完全背包问题，下文将一一讲解。
    【0-1 背包】
    该题的常见描述是：

• 有一个载重 W 的背包和 N 个物品。
• 每个物品具有价值 Val 和重量 Wt 。
• 问用这个背包装东西，最多装多少价值。

由题目可知，有两个变化的状态 - 选择的物体和背包的容量，说明我们需要一个二维 DP Table。
dp[i][w] ** ：对于前 i 个物品，当前背包的容量是 w ，这种情况下可以装的最大值。
Base case ： dp[0][…] 和 dp[…][0] 一个是没有物品，和一个没有空间的情况。
转移方程 ：我们的选择分为【把物品 i 放进背包】和 【不把物品 i 放进背包】**

• 【把物品 i 放进背包】说明需要使用价值为 Wt[i] 的物品，所以当前 dp[i][j] 就是前一个选择的结果 dp[i-1][w-Wt[i-1]] 加上物品价值Val[i]。

• 【不把物品 i 放进背包】说明不使用 i 物品，凑出的最大价值就是前一个状态dp[i-1][w]。

  const dp = new Array(N+1).fill(0).map(()=>new Array(W+1).fill(0));
  for( let i = 1 ; i <= N ; i++ ){
  for( let w = 1 ; w <= W ; w++ ){
     dp[i][w] = w - Wt[i-1] < 0 ? dp[i-1][w] : Math.max(dp[i-1][w],dp[i-1][w-Wt[i-1]]+ Val[i])
  }
  }
  return dp[N][W]
  

  【完全背包】
  完全背包和 0-1 背包的区别在于物品的数量是无限的，这导致转移方程需要改写，除此之外基本一致。
  转移方程 ：我们的选择分为【把物品 i 放进背包】和 【不把物品 i 放进背包】

• 【把物品 i 放进背包】说明需要使用价值为 Wt[i] 的物品，所以当前 dp[i][j] 就是前一个选择的结果 dp[i][w-Wt[i-1]] 加上物品价值Val[i]。注意这里前一个选择是 i 而不是 0-1背包问题的 i-1 ，因为我们可以选择无限次。

• 【不把物品 i 放进背包】说明不使用 i 物品，凑出的最大价值就是前一个状态dp[i-1][w]。

  const dp = new Array(N+1).fill(0).map(()=>new Array(W+1).fill(0));
  for( let i = 1 ; i <= N ; i++ ){
  for( let w = 1 ; w <= W ; w++ ){
     dp[i][w] = w - Wt[i-1] < 0 ? dp[i-1][w] : Math.max(dp[i-1][w],dp[i][w-Wt[i-1]]+ Val[i])
  }
  }
  return dp[N][W]
  

  题型一 | 0-1背包

  题型串联

  1 分割等和子集

  【关键词】0-1 背包
  【题目描述**】
  给定一个只包含正整数的非空数组 num。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
  【题目示例**】 ``` 输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

**【DP 定义】**

   - **状态** ： 1.选择的数字 `i`  2.元素和 `sum`
   - **dp[i][sum]** ：对于前 `i` 个数字，当前数字和是 `sum` ，问这种情况是否存在。

【**Base Case**】

   - **dp[0][...] **表示没有选数字的情况，其实必定凑不了大于零的和，所以都赋值 false。
   - **dp[...][0]** 表示和为 0 , 不管有几个可选数字都不选即可以实现，所以都赋值 true 。

【**转移方程**】我们的选择分为**【把数字 `i` 放进求和集】**和 **【不把数字 `i` 放进求和集】**

   - **【把数字 `i` 放进求和集】**此时说明 `i` 和 `sum` 都增加，`dp[i][sum]` 等于前一个状态是 `dp[i-1][sum-num[i-1]]` 
   - **【不把数字 `i` 放进求和集】**说明此时的最大价值 `dp[i][sum]` 就是前一个状态`dp[i-1][sum]` 。

【**复杂度分析**】

   - **时间复杂度**：O(n*tot)
   - **空间复杂度**：O(n*tot)
```javascript
var canPartition = function(num) {
    const n = num.length;
    let tot = num.reduce((item,pre)=>item+pre,0);
    if( n === 0 || tot % 2 !== 0) return false;
    tot /= 2;
    const dp = new Array(n+1).fill(0).map(()=>new Array(tot + 1).fill(false));
    for( let i = 0 ; i <= n ; i++ ) dp[i][0] = true;
    for (let i = 1 ; i <= n ; i++){
        for(let sum = 1 ; sum <= tot ; sum++){
            dp[i][sum] = sum-num[i-1] < 0 ? dp[i-1][sum] : dp[i-1][sum] || dp[i-1][sum-num[i-1]];
        }
    }
    return dp[n][tot];
};

【空间压缩**】**
我们可以注意到 dp[i][sum] 只是通过 dp[i-1][sum] 获得，可以进行 DP Table 压缩。
需要注意的是 sum 应该是从后往前遍历，因为大的 sum 是通过小的 sum 值获得的。

var canPartition = function(num) {
    const n = num.length;
    let tot = num.reduce((item,pre)=>item+pre,0);
    if( n === 0 || tot % 2 !== 0) return false;
    tot /= 2;
    const dp = new Array(tot + 1).fill(false);
    dp[0] = true;
    for (let i = 0 ; i <= n ; i++){
        for(let sum = tot ; sum >= num[i] ; sum--){
            dp[sum] =  dp[sum] || dp[sum-num[i]];
        }
    }
    return dp[tot];
};

题型二 | 完全背包

题型串联

1 零钱兑换

【关键词】完全背包
【题目描述**】
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
【题目示例**】

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

【DP 定义】

• 状态 ： 1.选择的硬币 i 2.当前总金额 j
• dp[i][j] ：对于前 i 个数字，当前数字和是 j ，此时所需的最小硬币数。

【Base Case】

• dp[0][…] 表示没有选数字的情况，其实必定凑不了大于零的和，所以赋值最大值。
• dp[…][0] 表示和为 0 , 不管选哪个硬币,最终硬币个数个数都为 0 。

【转移方程】我们的选择分为【选择硬币 i】和 【不选择硬币 i】

• 【选择硬币 i】说明需要面值为 coins[i] 的硬币，所以当前 dp[i][j] 就是前一个选择的结果 dp[i][j-coins[i]] 加上新增硬币数 1。
• 【不选择硬币 i】说明不使用 i 硬币，凑出最小硬币数就是前一个状态dp[i-1][j]。

【复杂度分析】

• 时间复杂度：O(n*amount)

• 空间复杂度：O(n*amount)

  var coinChange = function(coins, amount) {
  if( coins.length===0 || amount < 0 ) return -1;
  const n = coins.length ; 
  const dp = new Array(n+1).fill(0).map(()=>new Array(amount+1).fill(Number.MAX_SAFE_INTEGER));
  for( let i = 0 ; i <= n ; i++ ) dp[i][0] = 0;
  for( let i = 1 ; i <= n ; i++ ){
     for( let j = 1 ; j <= amount ; j++ ){
         if( j - coins[i-1] < 0 ) dp[i][j] = dp[i-1][j];
         else dp[i][j] = Math.min(dp[i-1][j],dp[i][j - coins[i-1]]+1);
     }
  }
  return dp[n][amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[n][amount];
  };
  

  【空间压缩**】**
  我们可以注意到 dp[i][j] 只是通过 dp[i][j-coins[i]] 获得，可以进行 DP Table 压缩。由于是和当前状态 i 有关，所以 j 是从前往后遍历的。
  

  var coinChange = function(coins, amount) {
  if( coins.length===0 || amount < 0 ) return -1;
  const n = coins.length ; 
  const dp = new Array(amount+1).fill(Number.MAX_SAFE_INTEGER);
  dp[0] = 0;
  for( let i = 0 ; i < n ; i++ ){
     for( let j = 1 ; j <= amount ; j++ ){
         if( j - coins[i] >= 0 ) dp[j] = Math.min(dp[j],dp[j - coins[i]]+1);
     }
  }
  return dp[amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[amount];
  };
  

  2 零钱兑换 II

  【关键词】完全背包
  【题目描述**】
  给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
  【题目示例**】

  输入: amount = 5, coins = [1, 2, 5]
  输出: 4
  解释: 有四种方式可以凑成总金额:
  5=5
  5=2+2+1
  5=2+1+1+1
  5=1+1+1+1+1
  

  【DP 定义】

• 状态 ： 1.选择的硬币 i 2.当前总金额 j

• dp[i][j] ：对于前 i 个数字，当前数字和是 j ，此时的组合数。

【Base Case】

• dp[0][…] 表示没有选数字的情况，其实必定凑不了大于零的和，所以赋值0。
• dp[…][0] 表示和为 0 , 不管选哪个硬币,都可以选择【不选】那个方案，所以都赋值 1 。

【转移方程】我们的选择分为【选择硬币 i】和 【不选择硬币 i】

• 【选择硬币 i】说明需要面值为 coins[i] 的硬币，所以当前 dp[i][j] 就是前一个选择的结果 dp[i][j-coins[i]] 。
• 【不选择硬币 i】说明不使用 i 硬币，凑出最小硬币数就是前一个状态dp[i-1][j]。

【复杂度分析】

• 时间复杂度：O(n*amount)

• 空间复杂度：O(n*amount)

  var change = function(amount, coins) {
  const n = coins.length;
  if( !amount && !n ) return 1;
  if( amount < 0 || !n ) return 0;
  const dp = new Array(n+1).fill(0).map(()=>new Array(amount+1).fill(0));
  for( let i = 0 ; i <= n ; i++ ) dp[i][0] = 1;
  for( let i = 1 ; i <= n ; i++ ){
     for( let j = 1 ; j <= amount ; j++ ){
         if( j - coins[i-1] >= 0 ) dp[i][j] = dp[i][j - coins[i-1]] + dp[i-1][j];
         else dp[i][j] = dp[i-1][j];
     }
  }
  return dp[n][amount]
  };
  

  【空间压缩**】**
  我们可以注意到 dp[i][j] 只是通过 dp[i][j-coins[i]] 获得，可以进行 DP Table 压缩。由于是和当前状态 i 有关，所以 j 是从前往后遍历的。
  

  var change = function(amount, coins) {
  if( amount === 0 && coins.length === 0 ) return 1;
  if( amount < 0 || coins.length === 0 ) return 0;
  
  const dp = new Array(amount+1).fill(0);
  
  for(let i = 0 ; i * coins[0] <= amount ; i++ ) dp[i * coins[0]] = 1;
  for(let i = 1 ; i < coins.length ; i++ ){
     for(let j = 1 ; j <= amount ; j++){
         dp[j] += (j - coins[i] >= 0 )? dp[j-coins[i]] : 0 ;
     }
  }
  return dp[amount];
  };