动态规划 | 任先生的笔记库

# 一、动态规划

# 1、基本认知

动态规划的名称来源于 20 世纪 50 年代的一个美国数学家 Richard Bellman，是他在处理一类具有重叠子问题和最优子结构性质的问题时，想到的一种“动态”地求解问题的方法。

先如今以成为动态规划在算法竞赛、数据结构、机器学习等领域中不可或缺的知识之一。

# 2、解题步骤

核心思想：将问题划分为若干个子问题，并在计算子问题的基础上，逐渐构建出原问题的解。

步骤 1：定义状态
步骤 2：确定状态转移方程
步骤 3：初始化状态
步骤 4：计算原问题的解

# 拓展：递归原理

递归内部实现类似于 JavaScript 中的 DOM 事件流，由内到外。

TIP

DOM 事件流中事件传播的 🤔 边界：目标元素和 document

但在递归中，递入的边界是由我们手动指定的，且必须指定递归的结束条件（Base case）

场景：

阶乘

关键词：The factorial recursion，参考：Recursion in Python (opens new window)

function fact(n) {
  if (n === 1) {
    return n
  } else {
    return n * fact(n - 1)
  }
}

console.log(fact(5)) // 120

图示：

# 二、题目练习

# 1、斐波那契数列

LeetCode：斐波那契数列 (opens new window)

暴力递归

function fib(n: number): number {
  if (n <= 1) return n

  return fib(n - 1) + fib(n - 2)
}

记忆化搜索

function fib(n: number, meno: number[] = []): number {
  if (n <= 1) return n

  // 是否存在
  if (menu[n]) return menu[n]

  const res = fib(n - 1, memo) + fib(n - 2, memo)

  // 保存记忆
  memo[n] = res

  return res
}

动态规划

function fib(n: number): number {
  // 1、定义状态
  const dp: number[] = []

  // 2、初始状态
  dp[0] = 0
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    // 3、状态转换方程
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  // 4、返回计算结果
  return dp[n]
}

动态规划 + 状态压缩

function fib(n: number): number {
  if (n <= 1) return n

  // 1、定义状态
  // 2、初始状态
  let prev = 0
  let cur = 1

  for (let i = 2; i <= n; i++) {
    // 3、状态转换方程
    const newValue = prev + cur
    prev = cur
    cur = newValue
  }

  // 4、返回计算结果
  return cur
}

# 2、跳台阶

LeetCode：爬楼梯 (opens new window)

暴力递归

function jump(n: number): number {
  if (n <= 1) return 1

  return jump(n - 1) + jump(n - 2)
}

记忆化搜索

function jump(n: number, meno: number[] = []): number {
  if (n <= 1) return 1

  // 是否存在
  if (menu[n] !== 0) return menu[n]

  const res = jump(n - 1, memo) + jump(n - 2, memo)

  // 保存记忆
  memo[n] = res

  return res
}

动态规划

function fib(n: number): number {
  // 1、定义状态
  const dp: number[] = []

  // 2、初始状态
  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    // 3、状态转换方程
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  // 4、返回计算结果
  return dp[n]
}

动态规划 + 状态压缩

function fib(n: number): number {
  if (n <= 1) return 1

  // 1、定义状态
  // 2、初始状态
  let prev = 1
  let cur = 1

  for (let i = 2; i <= n; i++) {
    // 3、状态转换方程
    const newValue = prev + cur
    prev = cur
    cur = newValue
  }

  // 4、返回计算结果
  return cur
}

# 3、最大子数组和

LeetCode：爬楼梯 (opens new window)

动态规划

function maxSubArray(nums: number[]): number {
  const n = nums.length

  // 1、定义状态
  const dp: number[] = []

  // 2、初始状态
  dp[0] = nums[0]

  for (let i = 1; i < n; i++) {
    // 3、状态转换方程
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
  }

  // 4、返回计算结果
  return Math.max(...dp)
}

动态规划 + 状态压缩

function maxSubArray(nums: number[]): number {
  const n = nums.length

  // 1、定义状态
  // 2、初始状态
  let preValue = nums[0]

  let max = preValue

  for (let i = 1; i < n; i++) {
    // 3、状态转换方程
    preValue = Math.max(nums[i], nums[i] + preValue)

    max = Math.max(preValue, max)
  }

  // 4、返回计算结果
  return max
}

← 排序算法