动态规划 (案例一)

题目

有一座高度是 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);
    }
}

参考文章:https://juejin.im/post/5a29d52cf265da43333e4da7