# 一、动态规划

# 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
}
更新于 : 7/8/2024, 10:21:14 AM