[算法提高] 动态规划爬楼梯

喜欢ヅ旅行 2022-03-06 04:03 225阅读 0赞

**\[问题背景\] **

来源：LeetCode(力扣)

编号：[70. 爬楼梯][70.]

内容：

假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 *n* 是一个正整数。

**示例 1：**

输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶

**示例 2：**

输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶

** \[思路分析\]**

这个问题本质上是要把n拆分为若干1与若干2相加得到n的等式。

比如 1 + 1 + 1 = 3

1 + 2 = 3

2 + 1 = 3

一种常见的动态规划法会选择从结果开始倒推。假设到达第n级的方法数为n，那么我们反过来看看，第n级倒推一步的情况是什么呢？

有可能是从第n-1级上了一阶到第n级，也可能是从第n-2级上了两阶。

在到达第n-1级的所有办法的基础上，每种办法再上一阶即到。

或者在到达第n-2级的所有办法的基础上，每种办法一次再上2阶即到。

加起来就是到达第n级的所有办法。

(有人问如果从第n-2级上一阶再上一阶呢？那种方法其实属于从n-1级上一阶到第n级。)

因此，到第n-1级的办法数 + 到第n-2级的办法数 = 到第n级的办法数

f(n) = f(n-1) + f(n-2) (函数递归法)

c\[n\] = c\[n-1\] + c\[n-2\] (循环递进法)

以上是“转移方程”

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70][]

其实这个问题有个更简单的原型是LeetCode 的509.[斐波那契数][Link 1]

** \[代码求解\]**

class Solution{
    public:
    	int climbStairs(int n) {
    		if (n == 1) {
    			return 1;
    		}
    		else if (n == 2) {
    			return 2;
    		}
    		else{
    			/*如果递归 
    			return climbStairs(i-1) + climbStairs(i-2);
    			n太大会超时 
    			而且有很多值交叉重复计算浪费了时间 
    			*/
    			int c[n+1];
    			c[1] = 1;
    			c[2] = 2;
    			for (int i = 3; i <= n; i++){
    				c[i] = c[i-1] + c[i-2]; //用空间换时间 
    			}
    			return c[n];
    		}
    	}
    };

**\[方法总结\]**

对于动态规划，我们可以尝试从结果倒推一步，找到这个“**转移方程**”，和“**转移边界**”联合使用。

函数递归法很漂亮，而循环递进法则有两个优点：1.空间换时间，避免递归层次太多造成超时。2.对于那些重复计算了的值，可以用数组记录这些值，下次直接使用即可。

对于509.斐波那契数的代码在LeetCode上的表现，我自己的写的函数递归法执行用时40ms，内存消耗8.5MB；而循环递进法执行用时8ms，内存消耗8.4MB。

似乎有大佬说过绝大部分递归和循环可以互相转化，但也颇有争议，我没有证明过这个说法，但只要能够高效地解出问题，我想对初学阶段应该是足够了。

[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70]: /images/20220306/bc1a6a6b226b4a0691d9e92b5d7edcaf.png
[Link 1]: https://leetcode-cn.com/problems/fibonacci-number/