lc322. 零钱兑换中等hot

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

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

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

思路

- 假设给出的不同面额的硬币是[1, 2, 5]，目标是 120，问最少需要的硬币个数？

- 我们要分解子问题，分层级找最优子结构，看到这又要晕了哈，憋急~~ 下面马上举例。

- 这里我们使用「自顶向下」思想来考虑这个题目，然后用「自底向上」的方法来解题，
  体验算法的冰火两重天。

- dp[i]: 表示总金额为 i 的时候最优解法的硬币数

- 我们想一下：求总金额 120 有几种方法？下面这个思路关键了 !!!
  一共有 3 种方式，因为我们有 3 种不同面值的硬币。
  1.拿一枚面值为 1 的硬币 + 总金额为 119 的最优解法的硬币数量
    这里我们只需要假设总金额为 119 的最优解法的硬币数有人已经帮我们算好了，
    不需要纠结于此。(虽然一会也是我们自己算，哈哈)
    即：dp[119] + 1
  2.拿一枚面值为 2 的硬币 + 总金额为 118 的最优解法的硬币数
    这里我们只需要假设总金额为 118 的最优解法的硬币数有人已经帮我们算好了
    即：dp[118] + 1
  3.拿一枚面值为 5 的硬币 + 总金额为 115 的最优解法的硬币数
    这里我们只需要假设总金额为 115 的最优解法的硬币数有人已经帮我们算好了
    即：dp[115] + 1
    
  - 所以，总金额为 120 的最优解法就是上面这三种解法中最优的一种，也就是硬币数最少
    的一种，我们下面试着用代码来表示一下：
    
  - dp[120] = Math.min(dp[119] + 1, dp[118] + 1, dp[115] + 1);
    
  - 推导出「状态转移方程」：
    dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)
    其中 coin 有多少种可能，我们就需要比较多少次，那么我们到底需要比较多少次呢？
    当然是 coins 数组中有几种不同面值的硬币，就是多少次了~ 遍历 coins 数组，
    分别去对比即可
    
  - 上面方程中的 dp[119]，dp[118]，dp[115] 我们继续用这种思想去分解，
    这就是动态规划了，把这种思想，思考问题的方式理解了，这一类型的题目
    问题都不会太大。

var coinChange = function(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for(let i = 1; i <= amount; i++) {
    for(let coin of coins) {
      if(i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
};

时间复杂度:O(m * n) m n分别为金额总数和硬币种数

空间复杂度:O(m)

变种：零钱兑换II

题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

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

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

• 用一个一维DP数组 dp，长度为 amount+1。
• dp[i] 表示凑成金额 i 的组合数。
• 初始化：dp[0] = 1（凑成0金额只有1种方法——什么都不选）
• 外层循环硬币面额，内层循环金额
• 对每个硬币 coin，从 coin 到 amount 遍历金额 i：
  • dp[i] += dp[i - coin]

这样保证不会重复计算顺序不同的组合，符合无序组合的定义。

function coinChangeCombinations(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1; // base case

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }

  return dp[amount];
}

遍历 coins 外层，amount 内层

意思是：先固定使用的硬币面额顺序，再遍历金额。

比如先用面额1，遍历所有金额，记录方案数；再用面额2，同理；面额5同理。

因为是先固定coin顺序，保证硬币顺序不会影响结果（硬币面额的遍历顺序就是“组合顺序”），

这样 2+1 和 1+2 是一样的

因此这里计算的是无序组合数。

遍历 amount 外层，coins 内层

意思是：对于每个金额，尝试所有硬币。

这时金额先遍历，硬币面额后遍历，允许先用不同顺序的硬币组成金额。

这样对于金额 i，会把所有不同顺序的硬币组合都计数进来。

比如金额5时，2+1+2 和 1+2+2 会被先后计算，两者都会增加 dp[5]。

结果是有序排列数。

lc53. 最大子数组和/数组和/最大和简单hot

题目描述

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

子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路

状态转移方程f(i)=max{f(i−1)+nums[i],nums[i]}

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

时间复杂度:O(n)

空间复杂度:O(n)

降低空间复杂度用pre保存上一个最大连续数组的和

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

时间复杂度:O(n)

空间复杂度:O(1)

lc70. 爬楼梯简单hot

题目描述

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

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

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

示例 1：

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

示例 2：

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

思路

状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]

var climbStairs = function(n) {
  const dp = []
  dp[1] = 1
  dp[2] = 2
  for(let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
};

时间复杂度:O(n)

空间复杂度:O(n)

优化空间复杂度

var climbStairs = function(n) {
    if (n === 1) return 1;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        let res = a + b
        a = b
        b = res
        
    }
    return b
};

时间复杂度:O(n)

空间复杂度:O(1)

lc121. 买卖股票的最佳时机 I简单hot

题目描述

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

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

思路一

设置一个变量存放最小的值，一个变量存放求和的值

var maxProfit = function(prices) {
  if(!prices.length) return 0
  let min = prices[0]
  let sum = 0
  for(let i = 1; i < prices.length; i++) {
    if(prices[i] < min) min = prices[i]
    if(prices[i] - min > sum) sum = prices[i] - min
  }
  return sum
};

时间复杂度:O(n)

空间复杂度:O(1)

思路二：动态规划

对于这道题，我们可以使用动态规划来解决。这里我们只需要进行一次买入卖出。那到最后交易时，可能会有三种状态：

• dp[0]：一直没有买
• dp[1]：：到最后只买了一笔，未卖出
• dp[2]：：到最后只卖了一笔，并卖出

由于第一种状态未进行任何操作，所以可以不用记录。然后我们对后两种状态进行转移：

• dp[1] = Math.min(dp[1], prices[i])：前一天也是b1状态或者是没有任何操作，今天买入一笔变成b1状态；
• dp[2] = Math.max(dp[2], prices[i] - dp[1])：前一天也是s1状态或者是b1状态，今天卖出一笔变成s1状态；

var maxProfit = function(prices) {
  if(!prices.length) return 0
  let dp = [0, prices[0], 0]
  for(let i = 1; i < prices.length; i++) {
    dp[1] = Math.min(dp[1], prices[i])
    dp[2] = Math.max(dp[2], prices[i] - dp[1])
  }
  return dp[2]
};

时间复杂度:O(n)

空间复杂度:O(1)

lc122. 买卖股票的最佳时机 II中等hot

题目描述

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

示例 1:

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

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路一

跟上题的思路一相仿，这题显得更简单，只有当天比前一天的金额高利润就加上他们的差价

var maxProfit = function(prices) {
  let res = 0
  for(let i = 1; i < prices.length; i++) {
    if(prices[i] > prices[i - 1]) {
      res += (prices[i] - prices[i - 1])
    }
  }
  return res
};

时间复杂度:O(n)

空间复杂度:O(1)

思路

对于这道题目，我们可以使用动态规划来解答。每个点的状态描述：手里有股票或者没股票。

1. dp[i][0]表示：第 i 天手里没股票，至今（第 i 天）的最大收益。第 i 天手里没股票，有两种可能：

• 昨天也没持有股票：dp[i-1][0]
• 昨天买了股票，今天卖了: dp[i-1][1] + prices[i](注意⚠️dp[i - 1][1]是负数，所以这里是加)
• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

2. dp[i][1]表示：第 i 天手里有股票，至今（第 i 天）的最大收益。第 i 天手里有股票，有两种可能：

• 昨天也有股票：dp[i-1][1]
• 昨天卖了，今天买了: dp[i-1][0] - prices[i]
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

最终目标是求出：dp[prices.length-1][0]和dp[prices.length-1][1]的较大者，前者肯定>=后者，求dp[prices.length-1][0]即可。

对于开始：

• day 0 没买:dp[0][0] = 0
• day 0 买了:dp[0][1] = -prices[0]

function maxProfit(prices) {
  const len = prices.length;
  if (len < 2) {
    return 0;
  };
  const dp = new Array(len);
  dp[0] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    dp[i] = new Array(2);
    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[len - 1][0];
}

• 时间复杂度： O(n)，其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。
• 空间复杂度：O(n)，我们需要开辟O(n) 空间存储动态规划中的所有状态。

lc198. 打家劫舍中等hot

题目描述

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

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

示例 1：

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

示例 2：

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

思路

首先来看最简单的两种情况，如果只有一间房屋，那这个屋子就是最高的金额，如果有两间房屋，那不能同时偷，只能偷其中其中金额高的那间，如果大于两间屋子，就要进行讨论了。

• 如果偷第n个房间，那么就不能偷第n - 1个房间，那么总金额就是前n - 2间屋子能偷到的最高的金额之和；
• 如果不偷第k间屋，那么能偷到的总金额就是前k - 1个房间的最高总金额。

这两者，我们只要取总金额的较大值即可。

我们可以用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i] = max(dp[i − 2] + nums[i], dp[i − 1])

边界条件为：

• dp[0] = 0 ：
• dp[1] = nums[0]：只有一间房屋，则偷窃该房屋

最终的答案即为 dp[n]，其中 n 是数组的长度。

var rob = function(nums) {
  let len = nums.length
  if(!len) return 0
  if(len === 1) return nums[0]

  let dp = new Array(len)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])
  for(let i = 2; i < len; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
  }
  return dp[len - 1]
};

滚动变量优化空间复杂度

var rob = function(nums) {
  let prev1 = 0, prev2 = 0;
  for (let num of nums) {
    let temp = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = temp;
  }
  return prev1;
};

lc213. 打家劫舍 II中等hot

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

思路：动态规划

打家劫舍这类问题其实都可以使用动态规划来解答，这个题目和打家劫舍类似，不过就是多了两种情况：

• 不偷第一家
• 不偷最后一家

这样就可以分类讨论，当不偷第一家时，就排除到第一家，对其他家进行计算，当不偷最后一家时，就排除掉最后一家，对其他家进行计算。

当前节点的最大值就是当前节点和之前的第二个节点的和与上个节点的值的最大值，这样说可能比较绕，状态转移方程代码：

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  if (n === 2) return Math.max(nums[0], nums[1]);

  // 线性偷窃问题
  function robLinear(arr) {
    let prev1 = 0, prev2 = 0;
    for (let num of arr) {
      let temp = Math.max(prev1, prev2 + num);
      prev2 = prev1;
      prev1 = temp;
    }
    return prev1;
  }

  // 情况 1：不偷最后一个
  const res1 = robLinear(nums.slice(0, n - 1));
  // 情况 2：不偷第一个
  const res2 = robLinear(nums.slice(1));

  return Math.max(res1, res2);
};

• 时间复杂度：O(n)，其中n是数组的长度，我们需要遍历两次数组；
• 空间复杂度：O(1)

lc337. 打家劫舍 III中等

题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1：

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2：

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

对于每个节点，有两个选择：

1. 偷这个节点（则不能偷左右孩子）
2. 不偷这个节点（可以偷左右孩子）

我们定义一个函数 robTree(node)，返回两个值：

[
  偷这个节点的最大收益,
  不偷这个节点的最大收益
]

状态转移公式：

robTree(node) = [
  node.val + left[1] + right[1],     // 偷当前节点：左右只能不偷
  Math.max(left[0], left[1]) + Math.max(right[0], right[1])  // 不偷当前节点：左右可以偷也可以不偷
]

var rob = function(root) {
  function dfs(node) {
    if (!node) return [0, 0];  // [偷这个节点，不偷这个节点]

    const left = dfs(node.left);
    const right = dfs(node.right);

    const doRob = node.val + left[1] + right[1]; // 偷这个节点
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不偷这个节点

    return [doRob, notRob];
  }

  const result = dfs(root);
  return Math.max(result[0], result[1]);
};

lc718. 最长重复子数组/公共最长中等hot

题目描述

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

示例 1：

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

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

思路

对于这道题目，我们可以使用动态规划来解决。动态规划就是要保持上一个状态和下一个状态有关系，并且是连续的。这里的子数组就相当于子串，是连续的。

这里我们初始化一个dp数组保存当前的最大连续值，dp[i][j]表示数组A的前i个元素和数组B的前j个元素组成的最长公共子数组的长度。

在遍历数组时：

• 如果当前的两个元素的值相等，也就是A[i] === B[j]，则说明当前的元素可以构成公共子数组，所以让前一个元素的最长公共子数组的长度加一，此时的状态转移方程是：dp[i][j] = dp[i - 1][j - 1] + 1；
• 如果当前的两个元素的值不相等，所以此时的dp值保存为0（初始化为0）。

在遍历的过程中，不断更新最长公共子序列最大值。

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

• 时间复杂度:O(mn)，其中m和n分别是nums1和nums2两个数组的长度，这里我们需要两层遍历两个数组。
• 空间复杂度:O(mn)，其中m和n分别是nums1和nums2两个数组的长度，我们需要初始化一个dp二维数组来保存当前的最长公共子数组的长度。

滚动数组优化空间复杂度

dp[i][j] 只用到了 dp[i - 1][j - 1] —— 也就是说：我们每次只需要上一行的数据。

于是我们可以把二维数组压缩为两行，甚至只保留一行来滚动复用。

var findLength = function(nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  let dp = Array(n + 1).fill(0); // 初始化上一行

  let maxLen = 0;

  for (let i = 1; i <= m; i++) {
    let newDp = Array(n + 1).fill(0); // 当前行
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        newDp[j] = dp[j - 1] + 1;
        maxLen = Math.max(maxLen, newDp[j]);
      }
    }
    dp = newDp; // 更新上一行
  }

  return maxLen;
};

时间复杂度:O(mn)

空间复杂度:O(n)

lc152. 乘积最大子数组中等hot

题目描述

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

示例 1:

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

示例 2:

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

思路：动态规划

var maxProduct = function (nums) {
  if (!nums.length) return null
  let state = [], max = nums[0];
  for (let i = 0; i < nums.length; i++) {
      state[i] = [];
  }

  state[0][0] = nums[0]; // 从 0 至 0 处的最大值
  state[0][1] = nums[0]; // 从 0 至 0 处的最小值

  for (let i = 1; i < nums.length; i++) {
    	// 连续的正整数state[i - 1][0] * nums[i] 连续的负整数nums[i],state[i - 1][1] * nums[i]
      state[i][0] = Math.max(state[i - 1][0] * nums[i], nums[i],state[i - 1][1] * nums[i]);
      state[i][1] = Math.min(state[i - 1][1] * nums[i], nums[i],state[i - 1][0] * nums[i]);
      if (max < state[i][0]) max = state[i][0]
  };
  return max
}

时间复杂度:O(n)

空间复杂度:O(n)

优化空间复杂度

var maxProduct = function (nums) {
  if (!nums.length) return null

  let maxProd = nums[0];
  let minProd = nums[0];
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    const prevMax = maxProd;

    maxProd = Math.max(num, num * maxProd, num * minProd);
    minProd = Math.min(num, num * prevMax, num * minProd);

    result = Math.max(result, maxProd);
  }

  return result;
}

时间复杂度:O(n)

空间复杂度:O(1)

lc62. 不同路径中等hot

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：m = 3, n = 3
输出：6

思路

每一个网格的路径数都和其上侧和左侧的路径数相关，可以得出递推方程：

a[i][j] = a[i - 1][j] + a[i][j - 1]

首先初始化一个 m * n 的二维数组，数组的所有节点值都先初始为0，由于最上边一行和最左边一列都是边界，只能有一种走法，所以初始为1。然后根据递推方程求解即可

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

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

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

• 时间复杂度:O(mn)，其中m和n分别是网格的长宽，我们需要两层遍历，所以空间复杂度为O(mn)。
• 空间复杂度:O(mn)，其中m和n分别是网格的长宽，我们需要一个m * n 的二维数组来存储所有状态，所以所需空间复杂度为O(mn)

滚动数组优化

为什么可以压缩成一维？

注意，在计算 dp[i][j] 时，我们只用到 当前行的左边值 和 上一行的当前位置。

所以我们可以让 一维数组 dp[j] 表示当前列的路径数：

• dp[j]：上一次遍历（上一行）中，到达 (i-1,j) 的路径数
• dp[j - 1]：当前行中，左边 (i,j-1) 的路径数（我们刚刚更新过）

于是，我们可以写：

dp[j] = dp[j] + dp[j - 1];

含义：

• 新的 dp[j] = 来自上方 + 来自左边

var uniquePaths = function(m, n) {
  const dp = Array(n).fill(1); // 第一行初始化为 1
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  return dp[n - 1];
};

lc63. 不同路径 II中等hot

题目描述

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

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

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

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

示例 1：

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

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

思路

这道题很简单，就是添加一个判断不等于0就跳过

var uniquePathsWithObstacles = function(obstacleGrid) {
  if(!obstacleGrid.length || obstacleGrid[0][0] === 1) return 0
  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 i = 0; i < n && obstacleGrid[0][i] === 0; i++) {
    dp[0][i] = 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]
};

时间复杂度:O(mn)

空间复杂度:O(mn)

滚动数组优化

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

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

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (obstacleGrid[i][j] === 1) {
        dp[j] = 0; // 遇到障碍物，路径数为 0
      } else if (j > 0) {
        dp[j] += dp[j - 1];
      }
    }
  }

  return dp[n - 1];
};

lc64. 最小路径和中等hot

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

示例 1：

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

思路

跟上面的不同路径思路一样

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

  for(let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i - 1] + grid[0][i]
  }

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

时间复杂度:O(mn)

空间复杂度:O(mn)

优化一下空间复杂度

var minPathSum = function(grid) {
  let m = grid.length, n = grid[0].length
  
  for(let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0]
  }

  for(let i = 1; i < n; i++) {
    grid[0][i] += grid[0][i - 1]
  }

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

时间复杂度:O(mn)

空间复杂度:O(1)

lc120. 三角形最小路径和中等hot

题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

与上题类似

var minimumTotal = function(triangle) {
  const n = triangle.length

  for(let i = 0; i < n; i++) {
    for(let j = 0; j <= i; j++) {
      if(i === 0 && j === 0) continue
      if(j === 0) triangle[i][j] += triangle[i - 1][j]
      else if(j === i) triangle[i][j] += triangle[i - 1][j - 1]
      else triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
    }
  }
  return Math.min(...triangle[n - 1])
};

• 时间复杂度：O(n^2)，其中 n 是三角形的行数。
• 空间复杂度：O(1)。这里我们在原数组的基础上进行的操作，所以所需要的额外的空间为常数。

lc516. 最长回文子序列中等hot

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

思路

与这题类似

我们考虑区间 [i...j]：

• 如果 s[i] == s[j]：
  • 那么这两个字符可以作为回文的两端
  • 中间 [i+1...j-1] 的最长回文子序列我们已知是 dp[i+1][j-1]
  • 所以 dp[i][j] = dp[i+1][j-1] + 2
• 如果 s[i] != s[j]：
  • 那么 s[i] 和 s[j] 至少有一个不能参与回文
  • 所以我们考虑：
    • dp[i+1][j]（跳过左边）
    • dp[i][j-1]（跳过右边）
  • 取两者最大值： → dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

最后就是要[0, n]的最大值dp[0] [n - 1]

var longestPalindromeSubseq = function(s) {
    const n = s.length;

    // 创建二维数组 dp[n][n]，默认填充为 0
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    // 所有单个字符的最长回文子序列长度是 1
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 枚举子串长度从 2 到 n
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1; // 子串的右边界

            if (s[i] === s[j]) {
                // 如果两端字符相等，加上中间的回文长度
                dp[i][j] = len === 2 ? 2 : dp[i + 1][j - 1] + 2;
            } else {
                // 不相等，取两种情况的最大值
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    // 最终结果是整个字符串的回文子序列长度
    return dp[0][n - 1];
};

时间复杂度：O(n^2)

空间复杂度：O(n^2)

求区间最小值乘区间之和的最大值字节

题目描述

给定一个正整数数列a, 对于其每个区间, 我们都可以计算一个X值; X值的定义如下:

对于任意区间, 其X值等于区间内最小的那个数乘上区间内所有数和; 现在需要你找出数列a的所有区间中, X值最大的那个区间;

示例

数列a为: 3 1 6 4 5 2; 
则X值最大的区间为6, 4, 5, X = 4 * (6+4+5) = 60;

思路：单调栈 + 前缀和

1. 使用单调栈找到每个数左边第一个比它小的位置 left[i]

2. 使用单调栈找到每个数右边第一个比它小的位置 right[i]

3. 使用前缀和快速求任意区间和

4. 对于每个 a[i]，计算：

   sum = prefixSum[right[i] - 1] - prefixSum[left[i]] X = a[i] * sum

   更新最大值。

function maxXValueInterval(a: number[]): number {
  const n = a.length;
  const prefixSum = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefixSum[i + 1] = prefixSum[i] + a[i];
  }

  const left: number[] = new Array(n).fill(-1);
  const right: number[] = new Array(n).fill(n);

  // 找左边第一个比当前小的元素
  const stack1: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack1.length && a[stack1[stack1.length - 1]] >= a[i]) {
      stack1.pop();
    }
    if (stack1.length) left[i] = stack1[stack1.length - 1];
    stack1.push(i);
  }

  // 找右边第一个比当前小的元素
  const stack2: number[] = [];
  for (let i = n - 1; i >= 0; i--) {
    while (stack2.length && a[stack2[stack2.length - 1]] >= a[i]) {
      stack2.pop();
    }
    if (stack2.length) right[i] = stack2[stack2.length - 1];
    stack2.push(i);
  }

  let maxX = 0;
  for (let i = 0; i < n; i++) {
    const l = left[i] + 1;
    const r = right[i] - 1;
    const sum = prefixSum[r + 1] - prefixSum[l];
    const X = a[i] * sum;
    maxX = Math.max(maxX, X);
  }

  return maxX;
}

时间复杂度：前缀和预处理：O(n)

两次单调栈：O(n)

最后遍历计算最大 X 值：O(n)

lc1277. 统计全为 1 的正方形子矩阵中等

题目描述

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

示例 1：

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

示例 2：

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

思路

我们尝试挖掘f[i][j] 与相邻位置的关系来计算出 f[i][j] 的值。

如上图所示，若对于位置 (i, j) 有 f[i][j] = 4，我们将以(i, j) 为右下角、边长为 4 的正方形涂上色，可以发现其左侧位置 (i, j - 1)，上方位置 (i - 1, j) 和左上位置 (i - 1, j - 1) 均可以作为一个边长为 4 - 1 = 3 的正方形的右下角。也就是说，这些位置的的 f 值至少为 3，即：

f[i][j - 1] >= f[i][j] - 1

f[i - 1][j] >= f[i][j] - 1

f[i - 1][j - 1] >= f[i][j] - 1 将这三个不等式联立，可以得到：

var countSquares = function(matrix) {
  if(matrix.length === 0 || matrix[0].length === 0) return 0;
  let row = matrix.length, col = matrix[0].length, count = 0;
  let dp = JSON.parse(JSON.stringify(matrix));
  
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] !== 0) {
        // 如果不越界，那就求出以当前点为右下角的正方形边长
        if (i - 1 >= 0 && j - 1 >= 0) {
          dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
          count += dp[i][j]; // 边长是几，以当前点为右下角的正方形就有几个，通过观察可以得出此结论
        } else { // 如果越界了，也要加 1，至少当前点是1，可以计为一个正方形
          count += 1;
        }
      }
    }
  }
  return count;
};

时间复杂度:O(mn)

空间复杂度:O(mn)

lc221. 最大正方形中等hot

题目描述

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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

思路

上题是铺垫，每一个值为1的方格，都是左上方 1x1的正方形的基础上加1

计算dp的每个值有以下规则：

• 如果当前的值为0，此时该点不存在于正方形中，直接给dp[i][j]赋值为0；
• 如果当前的值为1，dp[i][j]的值由其上、左、左上的三个值的最小值决定，所以其状态转移方程是：

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

除此之外，我们还需要考虑二维矩阵的最左边一列和最上面一行，如果值是1，就直接将dp[i][j]赋值为1。

var maximalSquare = function(matrix) {
  const m = matrix.length, n = matrix[0].length
  let res = 0
  if(!matrix || m === 0 || n === 0){
    return 0
  }
  let dp = new Array(m)
  for(let i = 0; i < m; i++){
    dp[i] = new Array(n).fill(0)
  }

  for(let i = 0; i < m; i++) {
    for(let j = 0; j < n; j++) {
      if(matrix[i][j] === '1') {
        if(i === 0 || j === 0) {
          // 处理边界 
          dp[i][j] = 1
        }else {
          dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        }
        res = Math.max(dp[i][j], res)
      }
    }
  }
  return res * res
};

• 时间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们需要遍历二维矩阵中的每个元素来计算 dp 的值。
• 空间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们创建了一个和原始矩阵大小相同的数组 dp 来保存当前正方形的最大边长

滚动数组优化

var maximalSquare = function(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const dp = new Array(n + 1).fill(0); // 初始化多一位，避免越界
  let maxLen = 0;
  let prev = 0; // 表示 dp[i-1][j-1]，左上角

  for (let i = 1; i <= m; i++) {
    prev = 0;
    for (let j = 1; j <= n; j++) {
      const temp = dp[j]; // 保存当前 dp[j]（也就是上一行 dp[i-1][j]）
      if (matrix[i - 1][j - 1] === '1') {
        dp[j] = Math.min(dp[j], dp[j - 1], prev) + 1;
        maxLen = Math.max(maxLen, dp[j]);
      } else {
        dp[j] = 0;
      }
      prev = temp; // 更新 prev 为下一轮的左上角
    }
  }

  return maxLen * maxLen;
};

lc746. 使用最小花费爬楼梯简单

题目描述

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

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

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

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

思路：很简单的动态规划

var minCostClimbingStairs = function(cost) {
  const len = cost.length
  const dp = [cost[0], cost[1]]
  for(let i = 2; i < len; i++) {
    dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i]
  }
  return Math.min(dp[len - 1], dp[len - 2])
};

时间复杂度:O(n)

空间复杂度:O(n)

因为f(n) = Math.min(f(n - 1), f(n - 2)) + cost[i]，只和前两项有关系，用滚动数组优化空间复杂度

var minCostClimbingStairs = function(cost) {
  const len = cost.length
  const dp = new Array(3)
  dp[0] = cost[0]
  dp[1] = cost[1]
  for(let i = 2; i < len; i++) {
    dp[2] = Math.min(dp[0], dp[1]) + cost[i]
    dp[0] = dp[1]
    dp[1] = dp[2]
  }
  return Math.min(dp[0], dp[1])
};

时间复杂度:O(n)

空间复杂度:O(1)

lc72. 编辑距离困难hot

题目描述

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

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

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

示例 1：

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

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

思路

• 若 word1[i - 1] === word2[j - 1]：说明最后一位不用操作 → dp[i][j] = dp[i - 1][j - 1]
• 否则，考虑三种操作中的最优解：

dp[i][j] = 1 + min(
  dp[i - 1][j],    // 删除
  dp[i][j - 1],    // 插入
  dp[i - 1][j - 1] // 替换
)

删除：dp[i - 1][j] + 1

含义：删除 word1[i-1]，然后将 word1[0...i-2] 转换成 word2[0...j-1]。

例子：

word1 = "abc", word2 = "ab"
=> 删除 'c'

• 转移为： dp[i][j] = dp[i - 1][j] + 1

插入：dp[i][j - 1] + 1

含义：给 word1 末尾插入 word2[j-1]，那么我们需要先将 word1[0...i-1] 变成 word2[0...j-2]。

例子：

word1 = "ab", word2 = "abc"
=> 插入 'c'

• 转移为： dp[i][j] = dp[i][j - 1] + 1

替换：dp[i - 1][j - 1] + 1

含义：如果 word1[i-1] != word2[j-1]，我们把 word1[i-1] 替换为 word2[j-1]。

例子：

word1 = "abc", word2 = "adc"
=> 替换 'b' 为 'd'

• 转移为： dp[i][j] = dp[i - 1][j - 1] + 1

如果字符相等，就不需要操作，直接继承之前的结果：

if (word1[i-1] === word2[j-1]) {
  dp[i][j] = dp[i - 1][j - 1];
}

初始化 dp[i][0] = i

含义： 当 word2 是空字符串（长度为0）时，如何将 word1 的前 i 个字符转换成空字符串？

• 答案就是：删除 word1 的这 i 个字符，所以需要 i 次操作。

举例： word1 = "abc", word2 = ""

• 要把 "abc" 变成 ""，需要删除 'a'、'b'、'c'，共3次操作。

初始化 dp[0][j] = j

含义： 当 word1 是空字符串（长度为0）时，如何将空字符串变成 word2 的前 j 个字符？

• 答案就是：插入 j 个字符，需要 j 次操作。

举例： word1 = "", word2 = "abc"

• 要把 "" 变成 "abc"，需要插入 'a'、'b'、'c'，共3次操作。

var minDistance = function(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // 初始化第一行和第一列
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // 删除
          dp[i][j - 1],     // 插入
          dp[i - 1][j - 1]  // 替换
        );
      }
    }
  }

  return dp[m][n];
};

时间复杂度:O(mn)

空间复杂度:O(mn)

lc1143. 最长公共子序列中等hot

题目描述

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

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

思路

第一种就是text1[i]与text2[j]相等，就是说子序列的个数要在原来dp[i-1][j-1]的基础上+1 第二种就是text1[i]与text2[j]不相等,就取dp[i-1][j]和[i][j-1]；两者中的最大值。

var longestCommonSubsequence = function(text1, text2) {
  const dp = Array.from(new Array(text1.length + 1),() => new Array(text2.length + 1).fill(0));
    let res = 0;
    for(let i = 1; i <= text1.length; i++) {
      for(let j = 1; j <= text2.length; j++) {
        if(text1[i - 1] === text2[j - 1]){
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
        }
        res = Math.max(res,dp[i][j]);
      }
    }
  return res;
};

时间复杂度:O(mn)

空间复杂度:O(mn)

优化空间复杂度

dp[i-1][j] —— 上一行同列

dp[i][j-1] —— 当前行左边

dp[i-1][j-1] —— 上一行左边（左上角）

在滚动数组实现中：

• dp[j] 在循环开始时保存的是上一行 dp[i-1][j] 的值（因为还没更新）
• dp[j-1] 是当前行已经更新过的左边元素（dp[i][j-1]）
• 所以只用prev保存dp[i-1][j-1]即可

var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length, n = text2.length;
  // dp[j] 表示 text1 的当前行和 text2 的前 j 个字符的最长公共子序列长度
  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    let prev = 0; // 记录 dp[j-1] 上一行的值，即 dp[i-1][j-1]
    for (let j = 1; j <= n; j++) {
      let temp = dp[j]; // 暂存 dp[j] 的旧值，用于下一次循环更新 prev
      if (text1[i - 1] === text2[j - 1]) {
        dp[j] = prev + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = temp;
    }
  }

  return dp[n];
};

时间复杂度:O(mn)

空间复杂度:O(m)

lc983. 最低票价中等hot

题目描述

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

• 一张 为期一天 的通行证售价为 costs[0] 美元；
• 一张 为期七天 的通行证售价为 costs[1] 美元；
• 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

思路

状态转移方程

买一天的票 f(n) = f(n - 1) + cost[0]

买七天的票 f(n) = f(n - 7) + cost[1]

买三十天的票 f(n) = f(n - 30) + cost[30]

取最小值

function mincostTickets(days, costs) {
  const daySet = new Set(days);
  const maxDay = days[days.length - 1];
  const dp = new Array(maxDay + 1).fill(0);

  for (let i = 1; i <= maxDay; i++) {
    if (!daySet.has(i)) {
      dp[i] = dp[i - 1]; // 不是旅行日，继承前一天的票价
    } else {
      const cost1 = dp[Math.max(0, i - 1)] + costs[0];
      const cost7 = dp[Math.max(0, i - 7)] + costs[1];
      const cost30 = dp[Math.max(0, i - 30)] + costs[2];
      dp[i] = Math.min(cost1, cost7, cost30);
    }
  }

  return dp[maxDay];
}

时间复杂度：O(maxDay)

空间复杂度：O(maxDay)

lc416. 分割等和子集中等hot

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

思路

问题转化为在数组中选择一些元素，使它们的和等于总和的一半（target = sum / 2）

设 dp[i] 表示是否能凑出和为 i 的子集。

• dp[0] = true —— 空集可以凑出 0。
• 目标：返回 dp[target]，其中 target = sum / 2。

状态转移方程：

对每个数字 num，从后往前枚举 j：

dp[j] = dp[j] || dp[j - num]

含义：如果能凑出 j - num，那么就能凑出 j（加上这个 num）。

注意要从大到小遍历 j，以避免重复使用同一个数。

如果从前遍历的话，原数组是[1, 2, 3, 5]

dp[5] = true 是因为 dp[0] + 5，然后你又用 dp[5] 去更新 dp[10] = dp[10] || dp[5]，这就相当于你用了两个 5 —— 不对 ❌

var canPartition = function(nums) {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const dp = Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }

  return dp[target];
};

时间复杂度:O(n * target)

空间复杂度: ``O(target)优化后的一维 DP