数据结构和算法: 动态规划-台阶问题

以下是我学习动态规划时的笔记, 也是常见的问题. 希望能通过本篇几个问题帮助你更好的理解动态规划

问题: 一个10级台阶, 每次只能走1步或2步, 走到顶部有几种走法?

如果只剩最后一步, 那么有两种情况, 最后一步为8->10或9->10即走一步或两步, 如果0 -> 8有X中方法, 0 -> 9有Y种方法, 那么可以认为F(10) = F(9) + F(8), 依次类推, 得出公式F(n) = F(n-1) + F(n-2), 直到n=1或n=2时F(1) = 1, F(2) = 2

动态规划的重要概念

1.最优子结构

F(10) = F(9) + F(8)

2. 边界

F(1) = 1, F(2) = 2

3. 状态转移公式

F(n) = F(n-1) + F(n-2)

可以归纳出以下公式

F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2)（n>=3）

代码实现

递归
```python
def climbs(n):
if n < 1:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
return climbs(n-1) + climbs(n-2)
print(climbs(10))
"""
89
"""
```
以上方法会构建一颗二叉树, 高度是N, 但是需要重复计算很多节点, 因此时间复杂度就是节点个数, 约等于O(2^n)
采用缓存方式
```python
cache = {1:1, 2:2}
def fibs(n):
if n not in cache:
cache[n] = fibs(n-1) + fibs(n-2)
return cache[n]
print fibs(10)
"""
89
"""
```
采用缓存形式后仅需计算大约N次, 所以时间复杂度是O(n), 缓存形式要存储所有的结果, 空间复杂度会比较大为O(n)
采用自底向上的方法
```python
def fibs(n):
if n < 1:
return 0
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
count = 3
while count <= n:
res = a + b
a, b = b, res
count += 1
return b
print fibs(10)
"""
89
"""
```
以上能保证时间复杂度是O(n), 同时降低空间复杂为O(1)

变态台阶问题

如果一次可以上1个台阶, 也可以上2个, 也能上n个, 共有几种走法?

假设有5个台阶, 那么f(5) = f(4)+f(3)+f(2)+f(1)+f(0), 依次对应最后一步跳跃1, 2, .., 5个台阶.
同理, 其中f(4) = f(3)+f(2)+f(1)+f(0), 带入上式可得f(5)=2*f(4). 所以得出

状态转移方程: f(n) = 2 * f(n-1)

边界: f(1)=1, f(2)=2

def fibs(n):
    if n < 2:
        return n
    return 2 * fibs(n-1)

print(fibs(3))

#
4

理解

如果更好的理解动态规划, 一个印象比较深的是

2 = 1 + 1
3 = 2 + 1 而不是 3 = 1 + 1 + 1

也就是以空间换时间的思路