刷题日记：递推问题1-力扣.70.爬楼梯

原题如下：

https://leetcode-cn.com/problems/climbing-stairs/submissions/

分析：

首先这是什么题目类型？

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:13103f1b-cb7f-46cc-9ff3-38cb11bb555c

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5fad8033-3995-40cd-a474-36378d1edea3

思路：

从第一步开始无论爬1阶还是2阶，后面都有非常多种情况，正向逻辑不是很明了的时候，我们可以采用逆向思维，先考虑最后一步，

有两种情况，爬了1阶和爬了2阶。

我们假设dp[n]是爬到n阶的方法数，那么最后爬了1阶的情况，就是爬到n-1阶的情况，爬到n-1阶的情况就是dp[n-1]，另一种情况就是dp[n-2]。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0b7b82d0-c47a-48fb-b9b4-9b5436e7f8b3

dp[n] = dp[n-1] + dp[n-2]

这样递推公式就出来了。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c49f7652-b03e-493c-a738-7b5706c43f53

dp[0]就是我1阶也不爬的情况，那只能有一种情况，就是站着别动，所以dp[0]=1；

爬到第1阶也只有一种，就是从0阶爬了1阶，dp[1]=1；

有了dp[0]、dp[1]后面的情况就可以递推得到了。如dp[2] = dp[0] + dp[1] = 2；

。。。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a4ac2c73-dd45-4adf-8ea1-b98c9424d28d

首先是C++：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = f[1] = 1;
        for (int i=2; i1; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
};+

不错，消耗了6M内存，击败了100%的用户。

然后是JAVA版：

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

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

还是击败了100%的用户，不过内存消耗提高到了34.8M，击败了98.36的用户。

然后我们来写Python3的版本：

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [1] * (n+1);
        for i in range (2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:60be6a67-92b4-44e9-a10f-f8e34c5b47a3

速度上并不是很理想，时间来到了36ms，只击败了43.37%的用户，什么原因？因为Python对递归的支持不是那么友好，效率比较低。

内存消耗则介于C++和JAVA之间。

既然简洁就简洁到底，试试reduce函数：

class Solution:
    def climbStairs(self, n: int) -> int:
        return reduce(lambda x,y: x[-1:]+[sum(x[-2:])], [1]*(n-1), [1,1])[1]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2ff445ab-e65c-4667-8540-09be89b0aad0

解释一下：reduce接收一个初始数组[1,1]，然后经过n-1次迭代，每次迭代的结果还是长度为2的数组，其内容是 [数组的最后一个值, 数组最后两个值的和]，迭代完成后取数组第二位（下标为[1]）的值。

然后我们试试当下很火的Go语言：

//import "fmt"
func climbStairs(n int) int {
    //fmt.Println("Hello" + "World")
    var dp =  make([]int, n+1)
    dp[0] = 1
    dp[1] = 1
    var i int
    for i = 2; i < n+1 ; i++ {
      dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

哦豁？再一次地，战胜了100%的用户，内存开销只有1.9M，看起来比C++更加优异。

最后我们来试下Scala：

object Solution {
    def climbStairs(n: Int): Int = {
        val dp = new Array[Int](n+1)
        dp(0) = 1;
        dp(1) = 1;
        for (i  to n) {
            dp(i) = dp(i-1) + dp(i-2)
        }
        dp(n)
    }
}

嗯~，352ms，破了最慢记录，而且时间是倒二名的10倍，但是依然击败了96.15%的用户；

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:61b68189-e755-45fc-8446-587db469e2cb

咱们也试试scala的reduce方法，fold=允许接收默认参数的reduce，scala的类型检查比较严格，写起来并不是很优雅：

object Solution {
    def climbStairs(n: Int): Int = {
        (1 to n-1).map(List(_)).fold(List(1,1))((x:List[Int], y:List[Int]) => {List(x.last, x.sum)}).last
    }
}

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b77d1b59-d3e2-40d5-b998-1cb0ef8e184b

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3fd812c1-fd7c-435a-8748-d7eb6112de7d

在五种语言中，有3种超越了100%的用户，所以我们的思路和算法还是比较合适的。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5acedf22-ed43-4608-89d0-e2cc0749b3b0

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:191bb81e-4f40-47a5-b951-996c759e5027

1首先把这个问题归到最简单的0~2阶的情况，是否可以快速滴得到结果？

2然后假设N-1阶，N-2阶，N-3阶问题已经解决了，能否递推到N阶问题？

如果两个回答都是Yes，那么这就是一个递推问题。

而地推公式呢，就是基于N阶问题对应N-1阶，N-2阶…的函数，即dp[n] = F(dp[n-1], dp[n-2],…)

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:445eae20-5924-460f-ab80-962733490161

1、如果把条件改成每次可以爬1~3阶，初始值和递推公式又是怎样的呢？

2、力扣62题.不通路经，这是一个中等难度的递推问题，掌握了递推算法，你就会发现——其实它只是一盘豆芽菜。

https://leetcode-cn.com/problems/unique-paths/submissions/

最后的最后，我们玩点不一样的，尝试使用SQL来解决这个问题：

WITH RECURSIVE step (lv, ways) AS
(
SELECT 0 AS lv, 1 AS ways, 0 AS last_ways
UNION ALL
SELECT 1 AS lv, 1 AS ways, 1 AS last_ways
UNION ALL
SELECT lv + 1, ways + last_ways AS ways, ways AS last_ways FROM step WHERE lv > 0 AND lv  44
)
SELECT * FROM step WHERE lv IN (41, 42, 43, 44, 45)

因为力扣不支持SQL语言，所以我们在另外一个平台来执行这段代码(http://sqlfiddle.com/)，数据库我们选择了postgresSQL9.6，感兴趣的朋友可以自己尝试一下。

稍微解释下这个SQL的含义，正如你所见，第一行第二行是0阶和1阶的初始值（其实0阶在这没有作用，写出来只是方便理解），lv代表了阶数，ways代表当前阶有多少种走法，last_ways代表了当前阶的上一阶，即（n-1）阶有多少种走法。递推的逻辑在第三个SELECT里，即当前阶的走法dp(n) = dp(n-1) + dp(n-2)。

然后一直循环到了45阶，因为到了46阶的时候int就越界了。

如你所见，最终数据库用了2ms解决了这个问题，受限于平台我们没法看到内存情况，但是这个成绩还是比较不错的，这也是我常常反对把所有问题都放到高级语言来处理的原因，因为数据在传输和转换过程带来的开销常常远大于此。

之所以把SQL放在这里，是想要表明一种观点：算法的关键并不在于使用了何种语言，而是掌握某种思维方式，如果你愿意的话，多找几个石子就可以实现这个算法。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f93e41ab-a2cc-4988-93e0-cebb38f750c8

Original: https://www.cnblogs.com/zhuisuidefeng/p/15259639.html
Author: 追随的风
Title: 刷题日记：递推问题1-力扣.70.爬楼梯