动态规划

动态规划

# lc322. 零钱兑换中等hot

题目描述

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

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2

示例 3：

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

1
2

示例 4：

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

1
2

示例 5：

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

1
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] 我们继续用这种思想去分解，
    这就是动态规划了，把这种思想，思考问题的方式理解了，这一类型的题目
    问题都不会太大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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]
};

1
2
3
4
5
6
7
8
9
10
11
12

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

空间复杂度:O(m)

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

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2

示例 3：

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

1
2

状态转移方程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)
};

1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度: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
};

1
2
3
4
5
6
7
8
9
10

时间复杂度:O(n)

空间复杂度:O(1)

# lc70. 爬楼梯简单hot

题目描述

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

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

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

示例 1：

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

1
2
3
4
5

示例 2：

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

1
2
3
4
5
6

状态转移方程：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]
};

1
2
3
4
5
6
7
8
9

时间复杂度:O(n)

空间复杂度:O(n)

优化空间复杂度

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

1
2
3
4
5
6
7
8
9

时间复杂度: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, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

1
2
3
4

示例 2：

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

1
2
3

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

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
};

1
2
3
4
5
6
7
8
9
10

时间复杂度: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]
};

1
2
3
4
5
6
7
8
9

时间复杂度: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 。

1
2
3
4

示例 2:

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

1
2
3
4

示例 3:

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

1
2
3

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

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
};

1
2
3
4
5
6
7
8
9

时间复杂度:O(n)

空间复杂度:O(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])

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];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度： 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 。

1
2
3
4

示例 2：

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

1
2
3
4

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

如果偷第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

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

1
2
3
4
5
6
7
8
9
10
11
12

# lc213. 打家劫舍 II中等hot

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3
4

示例 3：

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

1
2

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

不偷第一家
不偷最后一家

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

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

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    let res1 = 0, res2 = 0
    if(len === 0) return 0
    if(len === 1) return nums[0]

    const dp = new Array(len)
    
    // 不偷第一家
    dp[0] = 0
    dp[1] = nums[1]
    for(let i = 2; i <= len - 1; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res1 = dp[len - 1]

    // 不偷最后一家
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i <= len - 2; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res2 = dp[len - 2]
    return Math.max(res1, res2)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(n)，其中n是数组的长度，我们需要遍历两次数组；
空间复杂度：O(n)，其中n是数组的长度，我们需要初始化一个长度为n的数组来保存当前节点的状态。

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

题目描述

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

示例 1：

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

1
2
3

示例 2：

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

1
2

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

这里我们初始化一个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
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

题目描述

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

示例 1:

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

1
2
3

示例 2:

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

1
2
3

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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度:O(n)

空间复杂度:O(n)

优化空间复杂度

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

  let min = 1, max = 1, sum = -Infinity
  for(let i = 0; i < nums.length; i++) {
    if(nums[i] < 0) [min, max] = [max, min]

    max = Math.max(nums[i] * max, nums[i])
    min = Math.min(nums[i] * min, nums[i])
    sum = Math.max(max, sum)
  }
  return sum
}

1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度:O(n)

空间复杂度:O(1)

# lc62. 不同路径中等hot

题目描述

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

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

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

示例 1：

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

1
2

示例 2：

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

1
2
3
4
5
6
7

示例 3：

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

1
2

示例 4：

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

1
2

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

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]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

# 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. 向下 -> 向下 -> 向右 -> 向右

1
2
3
4
5
6

示例 2：

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

1
2

这道题很简单，就是添加一个判断不等于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]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度:O(mn)

空间复杂度:O(mn)

# lc64. 最小路径和中等hot

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2

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

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]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度: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]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度: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）。

1
2
3
4
5
6
7
8

示例 2：

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

1
2

与上题类似

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])
};

1
2
3
4
5
6
7
8
9
10
11
12
13

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

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

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

与这题类似

这里我们尝试使用动态规划来解答，初始化一个dp二维数组来保存子串的长度，dp[i][j]表示s中的第i个字符到第j个字符组成的子串中，最长的回文序列的长度。

下面最重要的就是找出状态转移方程：

如果字符串s的第i个和第j个字符相同：f[i][j] = f[i + 1][j - 1] + 2
如果字符串s的第i个和第j个字符不相同：f[i][j] = max(f[i + 1][j], f[i][j - 1])

这里需要注意遍历时的顺序，i是从最后一个字符开始遍历的，j是从i+1开始向后遍历，这样就能保证每个子问题都计算好了。最后只要返回dp[0][len-1]即可

var longestPalindromeSubseq = function(s) {
  const len = s.length
  let dp = new Array(len)
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(0);
  }
  for(let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1
    for(let j = i + 1; j < len; j++) {
      if(s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[0][len - 1]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

题目描述

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

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

示例

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

1
2

与这题类似的思路，就是一个矩形，每个都依赖前一个区间的最小值

也是同样求矩形对角线的上方

let maxXValue = (arr) => {
  let n = arr.length;
  // 最小数组
  let min = Array.from(new Array(n), (_) => new Array(n));
  // 最大结果数组
  let res = Array.from(new Array(n), (_) => new Array(n));
  let max = Number.MIN_SAFE_INTEGER;
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      // 对角线则为他们的自身
      if (i == j) {
        min[i][j] = arr[i];
        res[i][j] = arr[i] * arr[i];
        continue;
      }
      // 每一行固定的i值，就让j和j-1的值进行比较，如果更小的话就替换
      if (arr[j] < min[i][j - 1]) {
        min[i][j] = arr[j];
        // 结果改变，就是先将原来的最小值res[i][j] = min*(原来区间) -> (res[i][j] / min + arr[j]) * arr[j]
        res[i][j] = (res[i][j - 1] * arr[j]) / min[i][j - 1] + arr[j] * arr[j];
      } else {
        // 当前值比原来的更大一点，最小值数组不变
        min[i][j] = min[i][j - 1];
        // 往原来的最大结果数组中追加arr[j] * min[i][j - 1]
        res[i][j] = res[i][j - 1] + min[i][j - 1] * arr[j];
      }
      // 比较一下
      max = Math.max(res[i][j], max);
    }
  }
  return max;
};
let a = [3, 1, 6, 4, 5, 2];
console.log(maxXValue(a)); // 60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 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.

1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

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

1
2
3
4
5
6
7
8
9
10
11

我们尝试挖掘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;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度: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

1
2

示例 2：

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

1
2

示例 3：

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

1
2

上题是铺垫，每一个值为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
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

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

题目描述

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

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

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

示例 1：

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

1
2
3
4
5

示例 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 。

1
2
3
4
5
6
7
8
9
10

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])
};

1
2
3
4
5
6
7
8

时间复杂度: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])
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度: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')

1
2
3
4
5
6

示例 2：

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

1
2
3
4
5
6
7
8

    //   h o r s e
    // r 1 2 2 3 4
    // o 2 1 2 3 4
    // s 3 2 2 2 3

1
2
3
4

dp[i][j] 为word1[i] 转换成word2[j]的操作次数

如果word1[i] === word2[j] 就可以不进行操作沿用word1[i-1]转换成word2[j-1]的操作次数

如果word1[i] !== word2[j] 选择 dp[i-1][j-1](替换) dp[i-1][j](插入) dp[i][j-1](删除) 最小的操作方式

故word1[i] === word2[j] 时 dp[i][j]=dp[i-1][j-1] word1[i] !== word2[j] 时 dp[i][j]=Math.min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1

var minDistance = function(word1, word2) {
  let m = word1.length + 1, n = word2.length + 1;
  const dp = Array.from(new Array(m), () => new Array(n).fill(0));
  for(let i = 1; i < m; i++) {
    dp[i][0] = i;
  }
  for(let i = 1; i < n; i++) {
    dp[0][i] = i;
  }

  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 - 1][n - 1];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度:O(mn)

空间复杂度:O(mn)

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

题目描述

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

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

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

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

1
2
3

第一种就是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;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度:O(mn)

空间复杂度:O(mn)

优化空间复杂度

var longestCommonSubsequence = function(text1, text2) {
  // 将空间优化为一位数组，还可以选择较短的字符串
  const dp = Array(text1.length + 1).fill(0);

  // 保存上一次dp中的两个数值
  // pre是前一个数据的上一个状态，即左上角数据，对应二维数组中的dp[i-1][j-1]
  // cur是当前数据的上一个状态，对应二维数组中的dp[i-1][j]
  let pre = 0,cur = 0;

  for(let i = 0;i < text2.length; i++){
    for(let j = 0; j < text1.length; j++){
      cur = dp[j + 1]
      if(text2[i] === text1[j]){
        dp[j + 1]=pre + 1;
      }else{
        dp[j + 1]=Math.max(dp[j],dp[j + 1])
      }
      pre=cur;
    }
    pre=0;
  }
  return dp[text1.length];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度:O(mn)

空间复杂度:O(m)

上次更新: 2022/03/21, 11:27:08