实例展示动态规划和多次递归的优化之间的关系

例子描述

在做LeetCode时候做到一道不算难的题目,第70道Climbing Stairs。题目描述如下:
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1
2
3
4
5
6
7
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解决方法

其实明眼人一眼就能看见,这不是正是斐波那契数列的求逆过程嘛。对的,确实如此,所以解决这个问题的方法可以用动态规划解决,但是由于是逆过程,又会使人很想用递归法求解,下面是一开始写的代码。

传统递归法

1
2
3
4
5
6
7
8
int climbStairs(int n)
{
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
else
return (climbStairs(n-1)+climbStairs(n-2));
}

上面这个代码确实很简洁,思路也很简单,问题就是在LeetCode上提交后会超时。
所以稍微考虑了一下想到了这题和斐波那契数列的关系,改用了动态规划缩短一下时间。

动态规划

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) 
{
vector<int> steps(n,0);
steps[0]=1;
steps[1]=2;
for(int i=2;i<n;i++)
{
steps[i]=steps[i-2]+steps[i-1];
}
return steps[n-1];
}

后面在LeetCode的讨论里面看到了一个人也是用递归法,想问怎么才能解决超时,下面是一个回答者的解法,很有意思,能看到动态规划本身就是为了解决多余次数的递归的设计意义。

改进版的递归法(实际上也是动态规划)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
unordered_map<int,int> cache;
int climbStairs(int n) {
if(cache.find(n)!=cache.end()) return cache[n];
int result = 0;
if (n == 0) result = 0;
else if (n == 1) result= 1;
else if (n == 2) result = 2;
else result = climbStairs(n-1) + climbStairs(n-2);

cache[n]=result;
return result;
}
};

答主的原话:Because you were doing recursion without memorization, then you end up recalculating lots of stuff . e.g: when calculating f(44)=f(43)+f(42), you first calculate f(43) , then you calculate f(42), while f(42) is already available when calculating f(43). So… use a cache to store all your intermediate results and return the result immediately if it’s already calculated .
所以其实也就是另外开辟空间对之前的结果作出记录,就是动态规划。

当然对于这题还有一种更节省空间复杂度的解法,也特别棒:

动态规划法的精简法

1
2
3
4
5
6
int climbStairs(int n) {
int a = 1, b = 1;
while (n--)
a = (b += a) - a;
return a;
}

对于解法的解释引用一下LeetCode里的原话——Variable a tells you the number of ways to reach the current step, and b tells you the number of ways to reach the next step. So for the situation one step further up, the old b becomes the new a, and the new b is the old a+b, since that new step can be reached by climbing 1 step from what b represented or 2 steps from what a represented.
其实这里就是因为用动态规划解决这个问题的时候只需要用到前两步的数据记录。再之前的记录会随着计算推进由于不再需要而被丢弃。

利用矩阵乘法解Fibonacci

主要是利用

左半部分矩阵形式我们暂且称为Q,那么所要求的第n个Fibonacci数为 $Q^{n-1}$ 所得矩阵的第一列第一行对应的值。

具体的证明可与参考LeetCode上这道题的solution(主要LaTeX用起来不方便,要写好多公式)
给出对应的Java代码:
(c++里面也有pow函数用来求a的b次方,但是像这里边的multiply()支持对二维数组直接计算还真不能。Java里的Math类功能确实强。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public int climbStairs(int n) {
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}

利用Fibonacci公式

$F_n=1/{\sqrt{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^{n}]}$

java解法:

1
2
3
4
5
6
7
public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}