算法@LeetCode:ClimbingStairs
Log
- 【170421】完成 01 版提交，并研究了答案
题目
【题目类型备注】
动态规划
提交
01
【语言】
Python
【时间】
170421
【思路】
（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）
这个题目可以抽象为：给定 n，求出所有仅包含 1、仅包含 2 或仅包含 1 与 2 的不同的序列，使每一个这样的序列和为 n。所谓不同，只要 1 与 2 的排列顺序不同即可。例如 [1, 1, 2] 与 [1, 2, 1] 为不同的序列。
这题虽然是动态规划题，但我硬生生做成了数列推导题，因为没能找到 n 规模与 n-1 规模之间的更可读的关系。
进一步思考，该问题可化为 P1 + P2：
- P1：在不考虑排列、仅考虑组合的情况下，有多少种不同的序列使序列和为 n（序列中只包含 1、只包含 2 或只包含 1 与 2）？
- P2：在 P1 的基础上，有多少种排列？
第一个问题比较简单：最多有 k 组答案。也就是说，由于 n 必定为 2k 或 2k+1 的表达之一，那么 2 在序列中最多有 k 个，每多 1 个 2 就多了 1 组新的答案；根据 2 在序列中取的位置不同，有不同的排列方式。
当 n-1 变为 n 时：（令 C(n, r) 表示从总量为 n 的总体里取 r 个元素进行组合，对应的全部可能组合数）
- 有 0 个 2 的那组答案：不变，只有 1 种排列
- 有 1 个 2 的那组答案：增加了 C(n, 1) - C(n-1, 1) 种排列
- 有 2 个 2 的那组答案：增加了 C(n, 2) - C(n-1, 2) 种排列
- 有 3 个 2 的那组答案：增加了 C(n, 3) - C(n-1, 3) 种排列
- ……
严格说来，最后再考虑下 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 的解法，真的全是用兔子数列解答的。。好吧或本题的递推式就是如此，认了。。
