动态规划

动态规划算法是一种解决复杂问题的算法。它通常用于优化问题，例如在最小化或最大化某种目标函数的情况下，寻找满足某些约束条件的最优解。动态规划算法的核心思想是将问题分解成子问题，并通过存储已解决的子问题的结果来避免重复计算，从而实现高效地求解问题的目标。

步骤

• 确定状态：定义状态表示原问题的子问题。
• 确定状态转移方程：根据状态的定义，列出状态转移方程。
• 确定边界条件：确定问题的边界条件，即最小子问题的解。
• 确定计算顺序：根据状态转移方程，确定计算状态的顺序。
• 计算最优解：根据状态转移方程和边界条件，计算出最优解。

动态规划算法具有一定的局限性，它只适用于那些满足无后效性和最优子结构性质的问题。无后效性指当前状态的求解只与之前的状态有关，而与之后的状态无关；最优子结构性质指原问题的最优解可以由其子问题的最优解推导出来。

爬楼梯

一个简单的动态规划问题：假设你要爬楼梯，楼梯有 n 个台阶，每次你只能爬 1 个或 2 个台阶。那么，你有多少种不同的爬楼梯方案？

• 确定状态：定义状态表示爬到第 i 个台阶的方案数；
• 确定状态转移方程：假设已经爬到第 i-1 个台阶，此时可以选择爬 1 个台阶，也可以选择爬 2 个台阶。如果选择爬 1 个台阶，则方案数为爬到第 i-1 个台阶的方案数；如果选择爬 2 个台阶，则方案数为爬到第 i-2 个台阶的方案数。因此，爬到第 i 个台阶的方案数为爬到第 i-1 个台阶的方案数加上爬到第 i-2 个台阶的方案数，即 f(i) = f(i-1) + f(i-2)。
• 确定边界条件：当 n=1 时，只有一种方案；当 n=2 时，有两种方案。
• 确定计算顺序：从小到大依次计算 f(1)、f(2)、f(3)、……、f(n)。
• 计算最优解：最终的结果为 f(n)。

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

最小权值

假设你有一个 n x m 的网格图，你从左上角开始走到右下角，每次只能向右或向下走一步，每个格子有一个数字代表它的权值。现在，你想要找到一条从左上角到右下角的路径，使得路径上所有格子的权值之和最小。请问，这个最小的权值和是多少？

• 确定状态：定义状态表示走到第(i, j)个格子时的最小权值和为 dp[i][j]。 确定状态转移方程：假设已经走到了第(i-1, j)和第(i, j-1)个格子，此时可以选择从(i-1, j)向下走一步，或者从(i, j-1)向右走一步，然后累加当前格子的权值。因此，走到第(i, j)个格子的最小权值和为 min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid[i][j]表示第(i, j)个格子的权值。
• 确定边界条件：当 i=0 或 j=0 时，dp[i][j]的值为前一行或前一列的 dp 值加上当前格子的权值。
• 确定计算顺序：从小到大依次计算 dp[0][0]、dp[0][1]、dp[0][2]、……、dp[n-1][m-1]。
• 计算最优解：最终的结果为 dp[n-1][m-1]。

function fn(grid) {
  const n = grid.length
  const m = grid[0].length
  const dp = Array(n)
    .fill(0)
    .map(() => Array(m).fill(0))

  dp[0][0] = grid[0][0]

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

  for (let j = 1; j < m; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j]
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    }
  }
  return dp[n - 1][m - 1]
}