[动态规划] 一、爬楼梯

题目

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
再比如，每次走2级台阶，一共走5步，这是另一种走法。我们可以简写成 2,2,2,2,2。

动态规划问题建模阶段

1级阶梯  F(1) = 1
2级阶梯  F(2) = 2
...
9级阶梯  F(9) = F(8) + F(7)
10级阶梯 F(10) = F(9) + F(8)

由此可见，每一次迭代，只要保留之前的两种状态，就可以推导新的状态。而不需要像备忘录那样保留全部子状态。

动态规划三个重要的概念

最优子结构：F(9) 和 F(8) 是 F(10) 的最优子结构
边界：当只有 1 或 2 级阶梯时，可直接得出答案，不需要继续简化，称 F(1) 和 F(2) 是问题的边界
状态转移公式：F(n) = F(n-1) + F(n-2)

动态规划求解问题阶段

<?php
namespace app\index\controller;

use PHPUnit\Framework\TestCase;

class Index extends TestCase
{
    /**
     * 动态规划（Dynamic Programming）
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public function dp(int $num)
    {
        if ($num < 1) {
            return 0;
        }
        if ($num == 1) {
            return 1;
        }
        if ($num == 2) {
            return 2;
        }

        $a = 1;
        $b = 2;
        $res = 0;
        for ($i = 3; $i <= $num; $i++) {
            $res = $a + $b;
            $a = $b;
            $b = $res;
        }
        return $res;
    }

    /**
     * 动态规划方法测试
     */
    public function dp_test()
    {
        $num = 30;
        $res = $this->dp($num);
        $this->assertEquals($res,1346269);
    }
}

参考：程序员小灰

本作品采用《CC 协议》，转载必须注明作者和本文链接