2 xr08255920 xr08255920 于 2016.02.14 13:59 提问

动态规划(DP)算法求出一个问题的所有解

具体问题是:
假设有一个楼梯共有N步,你每次可以爬1步或2步。请编写一个函数来计算,有多少种不同的方法可以爬到顶。
此题给出的解如下:

 int climbStaris(int n){
    if(n <= 1) return 1;
    if(n == 2) return 2;

    int p = 1, q = 2, curr;
    for( int i = 3; i <= n; ++i){
        curr = p + q;
        p = q;
        q = curr;
    }
    return curr;
}

我不是很懂这个for循环意思,为什么进行了这样的循环操作,就能得到这道题的所有解?这里面用到了动态规划吗,哪里体现出来了。

2个回答

caozhy
caozhy   Ds   Rxr 2016.02.15 06:44

如果有1层,那么有1种走法(p)
如果有2层,那么有2种走法(q)
如果有3层,有2个分支,一个先到1层,再到3层,一个是先到2层再到3层,所以是curr = p + q
我们让p始终表示i - 2层,q始终表示i - 1层
因此新的p就是原来的q,新的q就是原来的curr
因此可以知道,对于第i层,肯定是第n-2的方法数(p)+到第n-1的方法数(q)

这个算法无非就是把递归强行写成循环,没什么动态规划。

caozhy
caozhy   Ds   Rxr 2016.02.15 06:45

因此可以知道,对于第i层,肯定是第n-2的方法数(p)+到第n-1的方法数(q)
->
因此可以知道,对于第i层,肯定是第i-2的方法数(p)+到第i-1的方法数(q)

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!