理论基础

介绍

动态规划（dynamic programing）是一种常用的算法，主要用于最优问题的求解。其思路是通过将原问题分解为子问题，子问题有一个最优解，再将子问题的最优解组合起来得到原问题的最优解。动态规划算法的时间复杂度通常为 O(n^2) （多项式）。

必要条件

一个问题可以通过动态规划的思路解决，该问题具有两个必要条件：

  • 具有最优子结构特性

问题的子问题的解是最优的，并且子问题的最优解可以推到问题的最优解，就称该问题具有最优子结构特性

  • 具有重复子问题特性

求解当前子问题时存在重复特性，该子问题被分为多个子问题，有些子问题已经被计算过。换句话说，求解f(n)和f(n-1)都要求解f(n-2)，而且求解f(n)还要求解f(n-1)，所以存在重复求解f(n-2)的情况。

解题步骤

关于动态规划的解题步骤，我们需要先明白几个定义：

  • 状态

求解dp问题可以理解为求解dp数组。状态可以理解为数组的每个元素dp[i]，动态规划解题的关键之一在于定义状态的含义。

  • 状态转移方程

可以理解为描述问题和子问题关系的数学公式，例如，$f(n)=g(f(n-1))$

  • 自顶向下和自底向上

自顶向下就是先求f(n)，再求f(n-1)，再求f(n-2)。存在重复求解的缺点，所以可以用备忘表（Memoization）优化。

1
2
3
4
5
6
7
函数f(n)：

if(n === 0)
 return 0
for i=1 to n
 dp[i] = f(n-i)
return dp[n]

可以通过画节点来理解为什么是从顶到下。

自底向上就是先求f(1)，f(2)，再求f(n)。子问题按顺序求解，当求解某个子问题时，所依赖的更小子问题已经求解好了，可以直接使用

1
2
3
4
5
6
7
函数f(n)：

if(n === 0)
 return 0
for i=1 to n
 dp[i] = dp[i-1]+dp[i-2]
return dp[n]

自底向上的代码更简洁，所以可以作为首选。

  • base case

递归结束的条件。

解题步骤

  • 定义状态
  • 确定转移方程
  • 列举base case
  • 计算最优解
    • 自顶向下还是自底向上
    • 如何优化算法（剪枝，备忘录）

很多文章会分为5个步骤，而且描述也不同，但是这些文章本质都是解释同一类型的问题。大家在阅读的时候可以多看几篇相关的文章，总结出自己的理解模式。

算法讲解

理解动态规划的经典入门题就是求解斐波那契函数。如果没有学习动态规划，可能很多同学可以通过暴力递归求解。学习了动态规划后，你可以使用备忘录去存储已经计算过的结果，避免重复计算来优化算法。

暴力递归

1
2
3
4
5
6
const fib = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 2;

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

备忘录（自顶向下）

1
2
3
4
5
6
7
8
9
10
const fib = (n, memo = {}) => {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n in memo) return memo[n];

  result = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = result;

  return result;
};

自底向上

1
2
3
4
5
6
7
8
9
const fib = (n) => {
  const dp = [0, 1];

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

  return dp[n];
};

可以看到，每次计算dp[n]的时候，dp[i-1]，dp[i-2]都是已知的。这就是自底向上，按顺序求解问题。

爬楼梯问题

上述求解斐波那契函数可能还看不出动态规划算法里的状态和状态转移。接下来，我们通过举例”爬楼梯“的算法题来分析和理解什么是状态，什么是状态方程，以及体验如何拆分问题。

刷过leetcode的同学都知道有一个比较经典的题目叫做”爬楼梯“问题。这个问题本质就是写斐波那契函数的求解方法，可以参考上一节，本节重点理解动态规划。

  1. 怎么拆问题

思考如果你在第n个阶梯，你的上一步有两种情况：你在n-1阶梯，还要爬1阶；你在n-2阶梯，还要爬2阶。

对于第1种情况，你在n-1阶梯，那么你的上一步又有两种情况：n-2或者n-3。

以此类推，可以发现，你在第3个阶梯时，上一步的两种情况是在1阶梯或者2阶梯，有2种方法可以到达：1 → 2 → 3; 1 → 3。

你在第2阶梯时，上一步就是1阶梯，只有1种方法；

你在第1阶梯时，没有上一步，只有1种方法。

所以通过分析可知，处在n阶梯位置，要综合考虑n-1阶梯和n-2阶梯位置的方法，确切地说，就是这二者的和。我们可以用数学上的函数f(n)表示处在n阶梯上对应的方法数，那么f(n)=f(n-1)+f(n-2）。

  1. 考虑状态

上面假设的f(n)就是状态，其实我们已经定义好了状态，就是处在n阶梯上对应的方法数，对于动态规划算法，一般状态我们用dp变量描述，此处的数据结构可以简单地使用数组即可。

  1. 考虑状态方程

当前问题和子问题之间的递归关系式就是dp[n]=dp[n-1] +dp[n-2]。

参考资料

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share

快来参与讨论吧~