动态规划

# 动态规划

# 动态规划的思路

递归 + 记忆化 -> 递推
状态的定义：opt[n]，dp[n]
状态转移方程：opt[n] = best_of(opt[n - 1], opt[n - 2], ...)
最优子结构

# 动态规划、回溯、贪心对比

回溯（递归）- 重复计算
贪心 - 永远局部最优
动态规划 - 记录局部最优子结构/多种记录值

# 斐波那契数列

const fib = (n) => {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
};

1
2
3

const fib = (n) => {
  if (n <= 1) return n;
  const dp = [];
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

1
2
3
4
5
6
7
8
9
10

const fib = (n) => {
  if (n <= 1) return n;
  let dp0 = 0;
  let dp1 = 0;
  let dp = 1;
  for (let i = 2; i <= n; i++) {
    dp0 = dp1;
    dp1 = dp;
    dp = dp0 + dp1;
  }
  return dp;
};

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

# 爬楼梯 ✅

题目地址 (opens new window)

// 动态规划：dp[i] 表示爬到第 i 阶楼梯的方法数
// 时间复杂度 O(n)；空间复杂度 O(n)
const climbStairs = (n) => {
  // 爬 1 阶有 1 种方法，爬 2 阶有 2 种方法
  if (n <= 2) return n;

  // 初始化前两个状态
  const dp = [];
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    // 到达第 i 阶前，最后一步只能从第 i-1 阶或第 i-2 阶迈出
    dp[i] = dp[i-1] + dp[i-2];
  }

  // 返回爬到第 n 阶的方法总数
  return dp[n];
};

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

// 滚动变量：只保存前两个状态，将空间复杂度从 O(n) 优化为 O(1)
// 时间复杂度 O(n)；空间复杂度 O(1)
const climbStairs = function(n) {
  // 爬 1 阶有 1 种方法，爬 2 阶有 2 种方法
  if (n <= 2) return n;

  // dp1、dp2 分别表示爬到前两阶的方法数
  let dp1 = 1;
  let dp2 = 2;

  for (let i = 3; i <= n; i++) {
    // 当前阶的方法数等于前一阶与前两阶的方法数之和
    let dp = dp1 + dp2;

    // 状态向前滚动，为计算下一阶做准备
    dp1 = dp2;
    dp2 = dp;
  }

  // dp2 最终表示爬到第 n 阶的方法总数
  return dp2;
};

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

# 打家劫舍 ✅

题目地址 (opens new window)

// 动态规划：sum[i] 表示考虑下标 0 到 i 的房屋时能获得的最高金额
// 时间复杂度 O(n)；空间复杂度 O(n)
var rob = function(nums) {
  const n = nums.length;

  // 没有房屋时收益为 0；只有一间房屋时只能偷这一间
  if (n === 0) return 0;
  if (n === 1) return nums[0];

  // 初始化前两间房屋对应的最优结果
  const sum = [];
  sum[0] = nums[0];
  sum[1] = Math.max(nums[0], nums[1]);

  for (let i = 2; i < n; i++) {
    // 偷第 i 间：sum[i - 2] + nums[i]
    // 不偷第 i 间：sum[i - 1]；取两种选择中的较大值
    sum[i] = Math.max(sum[i - 2] + nums[i], sum[i - 1]);
  }

  // 最后一个状态就是偷完所有房屋能够获得的最高金额
  return sum[n - 1];
};

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

// 滚动变量：只保存前两个状态，将空间复杂度从 O(n) 优化为 O(1)
// 时间复杂度 O(n)；空间复杂度 O(1)
var rob = function(nums) {
  const n = nums.length;

  // 处理房屋数量小于 2 的边界情况
  if (n === 0) return 0;
  if (n === 1) return nums[0];

  // first 表示只考虑第 0 间房屋的最优结果，
  // second 表示考虑第 0、1 间房屋的最优结果
  let first = nums[0];
  let second = Math.max(nums[0], nums[1]);

  for (let i = 2; i < n; i++) {
    // 暂存更新前的 second，也就是 dp[i - 1]，供下一轮状态滚动使用
    let temp = second;

    // 在 “偷当前房屋” 和 “不偷当前房屋” 之间选择收益较大的方案
    second = Math.max(first + nums[i], second);

    // 状态向前滚动：下一轮的 first 应是当前轮原来的 second
    first = temp;
  }

  // second 最终表示偷完所有房屋能够获得的最高金额
  return second;
};

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

# 分发饼干 ✅

题目地址 (opens new window)

// 贪心算法：优先用最小且能满足孩子的饼干进行分配
// 时间复杂度 O(mlogm + nlogn)，m、n 分别是孩子数和饼干数
// 空间复杂度 O(1)（不计算 sort 内部使用的空间）
var findContentChildren = function(g, s) {
  // 将孩子的胃口和饼干尺寸从小到大排序；sort 会修改原数组
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);

  // child 表示已满足的孩子数量，同时也是下一个待满足孩子的下标
  // cookie 表示已处理的饼干数量，同时也是下一块待处理饼干的下标
  let child = 0,
    cookie = 0;

  while (child < g.length && cookie < s.length) {
    // 当前饼干能够满足当前孩子，就完成一次分配并检查下一个孩子
    if (g[child] <= s[cookie]) {
      child++;
    }

    // 当前饼干要么已经分配，要么尺寸太小无法满足当前孩子，继续检查下一块
    cookie++;
  }

  // child 就是最终得到满足的孩子数量
  return child;
};

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

# 三角形的最小路径和

题目地址 (opens new window)

const minimumTotal = (triangle) => {
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] =
        Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];
    }
  }
  return triangle[0][0];
};

1
2
3
4
5
6
7
8
9

const minimumTotal = (triangle) => {
  let dp = new Array(triangle.length + 1).fill(0);
  for (let i = triangle.length - 1; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
    }
  }
  return dp[0];
};

1
2
3
4
5
6
7
8
9

# 最大子数组和

题目地址 (opens new window)

var maxSubArray = function(nums) {
  let sum = 0; // 只用一个变量 sum 来维护对于当前 f(i) 的 f(i-1) 的值，从而将空间复杂度降为 O(1)
  let res = nums[0];

  for (let i = 0; i < nums.length; i++) {
    // 状态转移方程：f(i) = max{f(i−1) + nums[i], nums[i]}
    sum = Math.max(sum + nums[i], nums[i]);
    res = Math.max(res, sum);
  }

  return res;
};

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

# 乘积最大子数组

题目地址 (opens new window)

var maxProduct = function(nums) {
  const n = nums.length;
  const min = new Array(n).fill(0);
  const max = new Array(n).fill(0);
  min[0] = nums[0];
  max[0] = nums[0];

  for (let i = 1; i < n; i++) {
    min[i] = Math.min(min[i - 1] * nums[i], max[i - 1] * nums[i], nums[i]);
    max[i] = Math.max(max[i - 1] * nums[i], min[i - 1] * nums[i], nums[i]);
  }

  return Math.max(...max);
};

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

const maxProduct = (nums) => {
  const dp = new Array(2).fill(0).map(() => new Array(2).fill(0));
  dp[0][0] = nums[0]; // dp[i][0] 表示数组中下标从 0 到 i 的连续子数组的最小值，负数
  dp[0][1] = nums[0]; // dp[i][1] 表示数组中下标从 0 到 i 的连续子数组的最大值，正数
  let max = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const x = i % 2,
      y = (i - 1) % 2; // 滚动数组，因此上面只需要申请空间为 2 的二维数组就行了
    dp[x][0] = Math.min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]);
    dp[x][1] = Math.max(dp[y][1] * nums[i], dp[y][0] * nums[i], nums[i]);
    max = Math.max(max, dp[x][1]);
  }

  return max;
};

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

const maxProduct = (nums) => {
  let curMin = nums[0];
  let curMax = nums[0];
  let tempMin = 0;
  let tempMax = 0;
  let max = nums[0];

  for (let i = 1; i < nums.length; i++) {
    tempMin = curMin * nums[i];
    tempMax = curMax * nums[i];
    curMin = Math.min(tempMin, tempMax, nums[i]);
    curMax = Math.max(tempMax, tempMin, nums[i]);
    max = Math.max(max, curMax);
  }

  return max;
};

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

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

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

# 买卖股票的最佳时机

题目地址 (opens new window)

const maxProfit = (prices) => {
  let minPrice = Number.MAX_VALUE;
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    maxProfit = Math.max(prices[i] - minPrice, maxProfit);
    minPrice = Math.min(prices[i], minPrice);
  }
  return maxProfit;
};

1
2
3
4
5
6
7
8
9

# 买卖股票的最佳时机 II ✅

题目地址 (opens new window)

// 动态规划
// dp[i][0]：第 i 天结束时，手上不持有股票的最大利润
// dp[i][1]：第 i 天结束时，手上持有股票的最大利润
// 时间复杂度 O(n)：只遍历一次价格数组
// 空间复杂度 O(n)：使用了 n 行 2 列的二维数组
const maxProfit = (prices) => {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
  dp[0][0] = 0; // 第 0 天不持股，利润为 0
  dp[0][1] = -prices[0]; // 第 0 天持股，利润为买入花费的负数
  for (let i = 1; i < n; i++) {
    // 不持股 = max(昨天就不持股, 昨天持股今天卖出)
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    // 持股 = max(昨天就持股, 昨天不持股今天买入)
    // 与只能买卖一次不同，这里允许多次交易，所以用 dp[i-1][0] 而非 -prices[i]
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }
  return dp[n - 1][0]; // 最后一天不持股必然是最优解（清仓利润最大）
};

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

// 动态规划 + 空间优化
// dp0、dp1 分别对应上面的 dp[i][0]、dp[i][1]，
// 因为第 i 天的状态只依赖第 i-1 天，滚动变量即可，不用整个数组
// 时间复杂度 O(n)：只遍历一次价格数组
// 空间复杂度 O(1)：只用了常数个变量
const maxProfit = (prices) => {
  let dp0 = 0; // 不持股的最大利润
  let dp1 = -prices[0]; // 持股的最大利润
  for (let i = 1; i < prices.length; i++) {
    const temp0 = Math.max(dp0, dp1 + prices[i]); // 今天不持股
    const temp1 = Math.max(dp1, dp0 - prices[i]); // 今天持股
    dp0 = temp0;
    dp1 = temp1;
  }
  return dp0;
};

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

// 贪心
// 把整个价格曲线拆成若干上升区间，每个上升区间的涨幅都吃到，
// 等价于把所有相邻天的正差值累加起来
// 时间复杂度 O(n)：只遍历一次价格数组
// 空间复杂度 O(1)：只用了一个累加变量
const maxProfit = (prices) => {
  let profit = 0;
  for (let i = 0; i < prices.length; i++) {
    // i = 0 时 prices[i - 1] 为 undefined，比较结果恒为 false，不会出错
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]; // 只要今天比昨天高就“卖出”，锁定这段涨幅
    }
  }
  return profit;
};

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

# 买卖股票的最佳时机 III

题目地址 (opens new window)

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

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

const maxProfit = (prices) => {
  let buy1 = -prices[0]; // 进行第一次买操作获得的最大利润
  let sell1 = 0; // 进行一次买操作和一次卖操作获得的最大利润，即完成第一笔交易
  let buy2 = -prices[0]; // 在完成一笔交易的前提下，进行第二次买操作获得的最大利润
  let sell2 = 0; // 进行第二次卖操作获得的最大利润，即完成第二笔交易
  for (let i = 1; i < prices.length; i++) {
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, buy1 + prices[i]);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, buy2 + prices[i]);
  }
  return sell2;
};

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

# 买卖股票的最佳时机 IV

题目地址 (opens new window)

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

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

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

题目地址 (opens new window)

const maxProfit = (prices) => {
  const n = prices.length;
  const dp = new Array(n).fill(0).map(() => new Array(3).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]); // 手上持有股票的最大收益
    dp[i][1] = dp[i - 1][0] + prices[i]; // 手上不持有股票，并且处于冷冻期中的累计最大收益
    dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]); // 手上不持有股票，并且不在冷冻期中的累计最大收益
  }
  return Math.max(dp[n - 1][1], dp[n - 1][2]);
};

1
2
3
4
5
6
7
8
9
10
11

const maxProfit = (prices) => {
  let dp0 = -prices[0];
  let dp1 = 0;
  let dp2 = 0;
  for (let i = 1; i < prices.length; i++) {
    const temp0 = Math.max(dp0, dp2 - prices[i]);
    const temp1 = dp0 + prices[i];
    const temp2 = Math.max(dp1, dp2);
    dp0 = temp0;
    dp1 = temp1;
    dp2 = temp2;
  }
  return Math.max(dp1, dp2);
};

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

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

题目地址 (opens new window)

const maxProfit = (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] - fee);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }
  return dp[n - 1][0];
};

1
2
3
4
5
6
7
8
9
10
11

const maxProfit = (prices, fee) => {
  let dp0 = 0;
  let dp1 = -prices[0];
  for (let i = 1; i < prices.length; i++) {
    const temp0 = Math.max(dp0, dp1 + prices[i] - fee);
    const temp1 = Math.max(dp1, dp0 - prices[i]);
    dp0 = temp0;
    dp1 = temp1;
  }
  return dp0;
};

1
2
3
4
5
6
7
8
9
10
11

const maxProfit = (prices, fee) => {
  let [dp0, dp1] = [0, -prices[0]];
  for (let i = 1; i < prices.length; i++) {
    [dp0, dp1] = [
      Math.max(dp0, dp1 + prices[i] - fee),
      Math.max(dp1, dp0 - prices[i])
    ];
  }
  return dp0;
};

1
2
3
4
5
6
7
8
9
10

# 最长递增子序列

题目地址 (opens new window)

// 动态规划
var lengthOfLIS = function(nums) {
  const n = nums.length;
  if (n <= 1) return n;
  let res = 1;
  const dp = [];
  dp[0] = 1;
  for (let i = 1; i < n; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    res = Math.max(res, dp[i]);
  }
  return res;
};

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

// 二分查找
var lengthOfLIS = function(nums) {
  const n = nums.length;
  if (n <= 1) return n;
  const res = [nums[0]];
  for (let i = 1; i < n; i++) {
    if (nums[i] > res[res.length - 1]) {
      res.push(nums[i]);
    } else {
      let left = 0;
      let right = res.length - 1;
      while (left < right) {
        let mid = left + ((right - left) >> 1);
        if (nums[i] > res[mid]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      res[left] = nums[i];
    }
  }
  return res.length;
};

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

# 最长回文子序列

题目地址 (opens new window)

var longestPalindromeSubseq = function(s) {
  const n = s.length;
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

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

  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; 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][n - 1];
};

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

# 零钱兑换

题目地址 (opens new window)

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

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

# 编辑距离

题目地址 (opens new window)

const minDistance = (word1, word2) => {
  const m = word1.length;
  const n = word2.length;
  const dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let j = 1; j <= n; j++) {
    dp[0][j] = j;
  }
  // dp[i][j] 表示将 word1 的前 i 个字符变成 word2 的前 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];
};

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

# 贪心算法

贪心算法的核心：在对问题求解时，总是做出在当前看来最好的选择。

贪心算法的适用场景：

问题能够分解成⼦问题来解决，⼦问题的最优解能递推到最终问题的最优解。这种⼦问题最优解成为最优⼦结构。

贪⼼算法与动态规划的不同在于它对每个⼦问题的解决⽅案都做出选择，不能回退。

动态规划则会保存以前的运算结果，并根据以前的结果对当前进⾏选择，有回退功能。

# 买卖股票的最佳时机 II

题目地址 (opens new window)

关键条件：只能持有 1 股、买卖无数次、无交易手续费

方法一：贪心算法。时间复杂度为：O(n)。

var maxProfit = function(prices) {
  let profit = 0;
  for (let i = 0; i < prices.length; i++) {
    // 只要当天的股价大于前一天的股价，就卖出，累计利润
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
};

1
2
3
4
5
6
7
8
9
10

方法二：动态规划。时间复杂度为：O(n)。

var maxProfit = function(prices) {
  // dp0 表示第 i 天交易结束后手里没有股票的最大利润，dp1 表示第 i 天交易结束后手里有一支股票的最大利润
  // 它们的初始值为第 0 天交易结束后的最大利润
  let dp0 = 0,
    dp1 = -prices[0];
  for (let i = 1; i < prices.length; ++i) {
    // 如果第 i 天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票或者前一天结束的时候手里持有一支股票，此时需要将其卖出，获取 prices[i] 的收益
    let newDp0 = Math.max(dp0, dp1 + prices[i]);
    // 如果第 i 天交易完后手里有一支股票，那么可能的转移状态为前一天已经持有一支股票或者前一天结束的时候手里没有股票，此时需要买入一支，并减少 prices[i] 的收益
    let newDp1 = Math.max(dp1, dp0 - prices[i]);
    dp0 = newDp0;
    dp1 = newDp1;
  }
  return dp0;
};

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

双指针和滑动窗口递归、剪枝和回溯

首页

Choose mode

动态规划

# 动态规划

# 动态规划的思路

# 动态规划、回溯、贪心对比

# 斐波那契数列

# 爬楼梯 ✅

# 打家劫舍 ✅

# 分发饼干 ✅

# 三角形的最小路径和

# 最大子数组和

# 乘积最大子数组

# 买卖股票的最佳时机

# 买卖股票的最佳时机 II ✅

# 买卖股票的最佳时机 III

# 买卖股票的最佳时机 IV

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

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

# 最长递增子序列

# 最长回文子序列

# 零钱兑换

# 编辑距离

# 贪心算法

# 买卖股票的最佳时机 II