动态规划学习笔记

发表于 阅读次数：

初次接触动态规划，从一个简单例子入手

概念

官方概念晦涩难懂，这里不做描述，有兴趣的可以去看《运筹学》动态规划相关章节。

简单来说就是：给定一个问题，将这个问题拆分成若干个有关联的可以直接解决的子问题，同时把子问题的答案记录下来，减少重复计算，最后，根据子问题的答案，推导出原问题的答案的一种方法。

子问题间的关联一般可以通过函数关系式递推出来，这个地推关系式称为动态规划的基本方程。

基本思想（重点）

  1. 拆分成有关联的子问题
  2. 找出递推关系式并确定边界条件
  3. 保存历史结果，减少重复计算

举例说明

leetcode原题：《爬楼梯》

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

要爬到楼顶，会出现两种情况

  • 最后爬1个台阶到楼顶
  • 最后爬2个台阶到楼顶

假设要爬10阶到达楼顶

  • 要么从第9阶爬到楼顶；要么从第8阶爬到楼顶；即：f(10) = f(9) + f(8)
  • 要到达第9阶，要么从第8阶爬到第9阶；要么从第7阶爬到第9阶；即：f(9) = f(8) + f(7)
  • …
  • 依此类推；f(3) = f(2) + f(1)

得出递推关系式：f(n) = f(n - 1) + f(n - 2)

当只有2个台阶或者1个台阶的时候，单独列出：f(2) = 2; f(1) = 1；这就是边界条件。

递归求解

1
2
3
4
5
function climbStairs(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    return climbStairs(n - 2) + climbStairs(n -1)
}

是不是和《斐波那契数列》一样?

当你在leetcode提交代码时，你会发现：

超时了

这是为什么呢？

从前面的分析：

  • 要计算f(10), 先要计算出f(9)和f(8)；
  • 要计算f(9), 先要计算出f(8)和f(7)；
  • 要计算f(8), 先要计算出f(7)和f(6)；
  • …
  • 要计算f(3)，先要计算f(2)和f(1)；

得到如下树状图：

图片描述

递归的时间复杂度 = 递归的次数 * 每次递归的时间复杂度

前面的每个子问题的复杂度 = f(n - 1) + f(n - 2)，加法操作，为常数型，即为 O(1)。

问题的个数 = 递归的节点总数。由上面树状图可以知道 sum = 1 + 2 + 4 + 8 + ... 是一个等比数列，由等比数列求和公式，得出节点总数为 2^n - 1，所以时间复杂度为 O(2^n)。

所以，前面递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n)，是指数型的，当n变大时，很快就超时了。

由树状图可以看出：f(8)被计算了2次，f(7)被计算了3次，f(6)被计算了4次…，存在大量的重复计算，所以导致算法低效。

这时，我们需要把计算过的结果保存下来直接使用，减少重复计算

1
2
3
4
5
6
7
8
9
10
11
let temp = {}; // 来存储计算过的结果
function climbStairs(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    if (temp[n]) {
        return temp[n]; // 如果已经计算过，直接返回值
    } else {
        temp[n] = climbStairs(n - 2) + climbStairs(n -1); // 如果是第一次计算，保存在temp中。
        return temp[n];
    }
}

再去leetcode提交代码时，就不会超时了。

递归通常是从f(n)到f(1)的方向求解，通常被称为自顶向下的解法

动态规划求解

动态规划一般是从f(1)到f(n)的方向求解，通常被称为自底向上的解法

由递推公式 f(n) = f(n - 1) + f(n - 2) 可以知道，f(n)的结果只和他前面两个数相关，所以用两个变量 a 和 b 来存储，时间复杂度为 O(1)。

f(1) f(2) f(3) f(4) … f(10)
a = 1 b = 2 a = 1 + 2 = 3 b = 3 + 2 = 5 … b = a + b

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
var climbStairs = function(n) {
    if (n === 1) return 1;
     if (n === 2) return 2;
     let a = 1;
     let b = 2;
     let res = 0;
     for (let i = 3; i <=n; i++) {
         res = a + b;
         a = b;
         b = res;
     }
     return res;
 }

看完上面的例子，对动态规划有不有一定的认识了呢？

来多刷几道题巩固下：leetcode动态规划相关题目

感谢你的阅读。