动态规划

题干：找出连续子数组的最大和。

• 关键定义：dp[i] = 以 nums[i] 结尾的最大子数组和
• 转移：dp[i] = max(nums[i], nums[i] + dp[i-1])（要么自己开头，要么接上前面）

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

题干：m×n 网格，从左上到右下，只能向右或向下，有多少条不同路径。

var uniquePaths = function(m, n) {
  let dp = []
  dp[0] = new Array(n).fill(1) // 第一行全为 1
  for (let i = 1; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (j === 0) {
        dp[i] = [1] // 第一列全为 1
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      }
    }
  }
  return dp[m - 1][n - 1]
}

题干：m×n 网格每格有非负数，从左上到右下，路径数字总和最小。

var minPathSum = function (grid) {
  const m = grid.length, n = grid[0].length
  const dp = [[]]
  dp[0][0] = grid[0][0]
  // 分步初始化，不容易混乱
  for (let i = 1; i < m; i++) { dp.push([]); 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] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1])
    }
  }
  return dp[m - 1][n - 1]
}

题干：每次可以爬 1 或 2 个台阶，到第 n 阶有多少种方法。

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

题干：数组中选一天买入、之后一天卖出，求最大利润。

• 递减时找最小值，递增时计算差值

var maxProfit = function(prices) {
  let minPrice = prices[0]
  let maxProfit = 0
  for (let i = 1; i < prices.length; i++) {
    let price = prices[i]
    if (price < minPrice) {
      minPrice = price // 更新最低价
    } else {
      maxProfit = Math.max(maxProfit, price - minPrice)
    }
  }
  return maxProfit
}

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

题干：找出连续子数组的最大乘积。

• 有负数 → 最小值乘以负数可能变最大值 → 需要同时维护 dpMin

var maxProduct = function(nums) {
  let dp = [], dpMin = []
  dp[0] = nums[0]; dpMin[0] = nums[0]
  let max = nums[0]
  for (let i = 1; i < nums.length; i++) {
    let item = nums[i]
    dp[i] = Math.max(item, item * dp[i - 1], item * dpMin[i - 1])
    dpMin[i] = Math.min(item, item * dp[i - 1], item * dpMin[i - 1])
    max = Math.max(max, dp[i])
  }
  return max
}

题干：相邻房屋不能偷，求最大偷窃金额。DP 入门经典题。

var rob = function(nums) {
  let dp = []
  dp[0] = nums[0]
  dp[1] = Math.max(dp[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]
}

题干：在 0/1 矩阵中找出只包含 1 的最大正方形，返回面积。

• 关键：dp[i][j] = 以 (i,j) 为右下角能构成的最大正方形边长
• 取上、左、左上角 DP 的最小值再 +1

var maximalSquare = function(matrix) {
  let m = matrix.length, n = matrix[0].length
  let dp = [[]]
  let max = 0
  // 初始化第一行
  for (let j = 0; j < n; j++) {
    dp[0][j] = matrix[0][j] === '1' ? 1 : 0
    max = Math.max(max, dp[0][j])
  }
  // 初始化第一列
  for (let i = 1; i < m; i++) {
    if (!dp[i]) dp[i] = []
    dp[i][0] = matrix[i][0] === '1' ? 1 : 0
    max = Math.max(max, dp[i][0])
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === '1') {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        max = Math.max(max, dp[i][j])
      } else {
        dp[i][j] = 0
      }
    }
  }
  return max * max // 返回面积
}

题干：找出数组中最长严格递增子序列的长度。经典 DP。

• 注意是子序列（不要求连续），不是子数组
• 对每个 i，遍历 0~i-1，如果 nums[i] > nums[j] 就可以接上

var lengthOfLIS = function(nums) {
  let dp = new Array(nums.length).fill(1) // 每个元素自己就是长度 1
  let max = 1
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) { // 可以接在 j 后面
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
    max = Math.max(max, dp[i])
  }
  return max
}

题干：给定不同面额硬币和总金额，计算凑成总金额所需的最少硬币数。

var coinChange = function(coins, amount) {
  coins.sort((a, b) => a - b)
  let dp = []
  dp[0] = 0

  function getDpMin(dpIndex) {
    let min = Infinity
    for (let i = 0; i < coins.length; i++) {
      if (dpIndex >= coins[i]) {
        min = Math.min(min, dp[dpIndex - coins[i]])
      } else {
        break // 排过序，后面更大，直接剪枝
      }
    }
    return min
  }

  for (let i = 1; i <= amount; i++) {
    dp[i] = getDpMin(i) + 1
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}