视频字幕
今天我们来解决一个经典的动态规划问题：爬楼梯问题。假设有一个楼梯，有n个台阶，每次只能爬1步、2步或3步。问题是：要爬到楼顶，有多少种不同的爬法？这是一个典型的计数问题，我们可以用动态规划的思想来解决。
我们用动态规划来解决这个问题。设f(i)表示爬到第i个台阶的方法数。首先确定基本情况：f(0)等于1，表示不爬有一种方法；f(1)等于1，只能爬1步；f(2)等于2，可以爬1+1或直接爬2步。对于第3个台阶，可以从第0、1、2个台阶分别爬3步、2步、1步到达。
现在我们推导出递推关系。对于第i个台阶，当i大于等于3时，f(i)等于f(i-1)加f(i-2)加f(i-3)。这是因为要到达第i个台阶，最后一步可能是从第i-1阶爬1步，从第i-2阶爬2步，或从第i-3阶爬3步。以第5个台阶为例，f(5)等于f(4)加f(3)加f(2)。
让我们通过具体计算来验证这个递推关系。基本情况我们已经知道：f(0)等于1，f(1)等于1，f(2)等于2。然后我们可以计算f(3)等于f(2)加f(1)加f(0)，即2加1加1等于4。f(4)等于f(3)加f(2)加f(1)，即4加2加1等于7。f(5)等于f(4)加f(3)加f(2)，即7加4加2等于13。
总结一下，我们用动态规划解决爬楼梯问题的步骤是：首先定义状态f(i)表示爬到第i阶的方法数；然后确定基本情况；接着推导递推关系f(i)等于前三项之和；最后从小到大依次计算。这个算法的时间复杂度是O(n)，空间复杂度可以优化到O(1)。对于n个台阶，答案就是f(n)。