亮亮的笔记本

# 动态规划

  • 一般是求最值的问题

  • 重叠子问题、最优子结构、状态转移方程就是动态规划三要素

  • 动规是由前一个状态推导出来的，而贪心是局部直接选最优的

一般思路：

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

# 动态规划的核心原理

定义 dp 数组/函数的含义 -> 明确 base case -> 明确「状态」-> 明确「选择」

# 322.零钱兑换 (opens new window)

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // 初始化dp  dp[i]   i块钱需要dp[i]个最少硬币
  const dp = new Array(amount + 1).fill(amount + 1)
  dp[0] = 0
  for (let i = 0; i < dp.length; i++) {
    for (let coin of coins) {
      if (i - coin < 0) {
        continue
      }
      // 计算 min（dp[11-1],dp[11-2],dp[11-5]）  +1
      dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
  return dp[amount] === amount + 1 ? -1 : dp[amount]
}

# 300. 最长递增子序列 (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const n = nums.length
  const dp = new Array(n).fill(1)

  for (let i = 0; i < n; i++) {
    // nums[i] DP[i]
    // 遍历找到比j小的值
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        // dp[3] dp[j] +1 和dp[3] 的最大值
        dp[i] = Math.max(dp[j] + 1, dp[i])
      }
    }
  }
  let res = 0

  for (let i = 0; i < dp.length; i++) {
    res = Math.max(res, dp[i])
  }
  return res
}

# 198.打家劫舍 (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  // 初始化dp dp[i] 第i房间的时候 抢到的最高物品总价值
  const dp = new Array(nums.length)

  dp[0] = nums[0]
  dp[1] = Math.max(nums[1], nums[0])

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

# 买卖股票的最佳时机 (opens new window)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // dp[i][0] 第i天不持有股票的时候最大利润
  // dp[i][1] 第i天持有股票最大利润
  const dp = new Array(prices.length).fill().map((_) => [])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < prices.length; i++) {
    // 达到第i天不持有股票的状态
    // 昨天不持股，今天什么都不做；
    // 昨天持股，今天卖出股票（现金数增加）
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    // 如果第i天持有股票的状态
    // 昨天持股，今天什么都不做（现金数与昨天一样）；
    // 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）
    dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
  }
  return dp[prices.length - 1][0]
}

# 122. 买卖股票的最佳时机 II (opens new window)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // dp[i][0] 第i天不持有股票的时候现金 dp[i][1] 第i天持有股票最大现金
  const dp = new Array(prices.length).fill().map((_) => [])
  dp[0][0] = 0
  dp[0][1] = -prices[0]
  for (let i = 1; i < prices.length; i++) {
    // 达到第i天不持有股票的状态
    // 昨天不持股，今天什么都不做；
    // 昨天持股，今天卖出股票（现金数增加）
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    // 如果第i天持有股票的状态
    // 昨天持股，今天什么都不做（现金数与昨天一样）；
    // 昨天不持股，今天买入股票
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  }
  return dp[prices.length - 1][0]
}

← 接雨水 →