DP中的递归和n阶例子

Question

我是动态编程的新手，所以我看了这个例子。

你有N级台阶要爬。一次只能爬1、2级台阶。找到到达第n步的方法数。

其解为:T(n)=T(n-1)+T(n-2)

我做的最后一步是什么？

我不是在n-1步就是n-2步。现在怎么能达到第N步的路数是达到n-1步和n-2步的路数之和。我无法获得理解逻辑所需的直觉，请帮帮我。

附注：我可以用递归的方式编写代码。

Answer 1

到达第n-2步然后做2步的方法和到达第n-1步然后做1步的方法不相交，因为它的最后一步不同，没有其他方法可以到达第n步，不绕过(n-1)或(n-2)，那些已经为(n-1)和(n-2)计算过了

Answer 2

动态规划解法

T(n)=T(n-1)+T(n-2)基本上是求n第fibonacchi数的递推算法。现在，如果我正确理解了你的问题，你正在试图为此找到一个动态编程的解决方案。

使用DP我们只需对以前的答案保持记忆，并从以前的答案中计算出一个新的答案。这基本上归结为：

int[] s = new int[n]
s[0] = 0;
s[1] = 1;

for(int i = 2; i < n; i++) {
    s[i] = s[i - 1] + s[i - 2];
}

return s[n - 1] + 1;

其中，n是步骤数，s[n-1]+1是到达第n步骤的途径数。

因此，对于两个步骤，解决方案为(1)+1=2:

1 + 1
2

对于3个步骤，解决方案为(1+1)+1=3:

1 + 1 + 1
1 + 2
2 + 1

对于4个步骤，解决方案为(1+1+2)+1=5

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

对于5个步骤，解决方案为(1+1+2+3)+1=8

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 2
2 + 1 + 2
2 + 2 + 1

让我们深入一下

我做的最后一步是什么？

根据我们所得到的资料，这是无法确定的。最后一步纯粹取决于我们选择什么顺序走台阶。然而，我们能做的是找到最后一步是2步还是1步的概率。从上面的插图可以看出，最后一步为1的概率是：

P(1) = 1 / 1 = 100.0%
P(2) = 1 / 2 =  50.0%
P(3) = 2 / 3 =  66.6%
P(4) = 3 / 5 =  60.0%
P(5) = 5 / 8 =  62.5%

正如我们所看到的，分子和分母都遵循相同的模式；分子只是分母前面的一个斐波那基数。

因此,最后一步的概率为1：

F(n) = F(n - 1) + F(n - 2), F(0) = 0, F(1) = 1, n >= 0

P(n) = F(n) / F(n - 1), n >= 2

当n接近无穷大时，1/P(n)的递归公式实际上以(1+sqrt(5))/2为限，这可能更好地称为黄金比率。

知道了这一点，最后一步为1的概率是1/((1+sqrt(5))/2)，也可以写出2/(1+sqrt(5))。因为这是>0.5，我们可以说最后一步很可能是1。

您可以在Wolfram Alpha中看到完整的计算。