算法@LeetCode:ClimbingStairs

Log

• 【170421】完成 01 版提交，并研究了答案

题目

Climbing Stairs

【题目类型备注】

动态规划

提交

01

【语言】

Python

【时间】

170421

【思路】

（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）

这个题目可以抽象为：给定 n，求出所有仅包含 1、仅包含 2 或仅包含 1 与 2 的不同的序列，使每一个这样的序列和为 n。所谓不同，只要 1 与 2 的排列顺序不同即可。例如 [1, 1, 2] 与 [1, 2, 1] 为不同的序列。

这题虽然是动态规划题，但我硬生生做成了数列推导题，因为没能找到 n 规模与 n-1 规模之间的更可读的关系。

进一步思考，该问题可化为 P1 + P2：

1. P1：在不考虑排列、仅考虑组合的情况下，有多少种不同的序列使序列和为 n（序列中只包含 1、只包含 2 或只包含 1 与 2）？
2. P2：在 P1 的基础上，有多少种排列？

第一个问题比较简单：最多有 k 组答案。也就是说，由于 n 必定为 2k 或 2k+1 的表达之一，那么 2 在序列中最多有 k 个，每多 1 个 2 就多了 1 组新的答案；根据 2 在序列中取的位置不同，有不同的排列方式。

当 n-1 变为 n 时：（令 C(n, r) 表示从总量为 n 的总体里取 r 个元素进行组合，对应的全部可能组合数）

1. 有 0 个 2 的那组答案：不变，只有 1 种排列
2. 有 1 个 2 的那组答案：增加了 C(n, 1) - C(n-1, 1) 种排列
3. 有 2 个 2 的那组答案：增加了 C(n, 2) - C(n-1, 2) 种排列
4. 有 3 个 2 的那组答案：增加了 C(n, 3) - C(n-1, 3) 种排列
5. ……

严格说来，最后再考虑下 n 是从 2k+1 -> 2k 还是 2k -> 2k+1 即可。

于是大致裂了前 8 项，发现方案总数为 1, 2, 3, 5, 8, 13, 21, 34，方案增量为 1, 1, 2, 3, 5, 8, 13，很快就发现这是典型的兔子数列（斐波那契数列），于是很快就写出了表达式……

【代码】

class Solution(object):
    def climbStairs(self, n): 
        """ 
        :type n: int
        :rtype: int
        """
        if (0 == n) or (1 == n) or (2 == n): 
          return n
        
        diff = [0, 1]
        ways = 1 
        
        for i in range(2, n+1):
          ways += diff[i-1]
          diff.append(diff[i-1] + diff[i-2])
        
        return ways

【结果】

运行时：39 ms

报告链接：https://leetcode.com/submissions/detail/100748836/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 69.85% of python submissions.

硬生生把 DP 题写成了数列规律寻找题，不太好，要研究一下答案有没有更好的 DP 解法

00

参考解法：

看了 5 个以上号称 DP 的解法，真的全是用兔子数列解答的。。好吧或本题的递推式就是如此，认了。。