DonnieYeh 2016-02-14 05:59 采纳率: 0%
浏览 1875

动态规划(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条回答 默认 最新

  • threenewbee 2016-02-14 22: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)

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

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题