首页
登录 | 注册

Climbing Stairs爬楼梯——动态规划

题目描述:

初阶:有n层的台阶,一开始你站在第0层,每次可以爬两层或者一层。请问爬到第n层有多少种不同的方法?

进阶:如果每次可以爬两层,和倒退一层,同一个位置不能重复走,请问爬到第n层有多少种不同的方法?


解题思路:

初阶:一维动态规划。爬楼梯数目其实是一个斐波拉契数列。

假定f[i] 表示是爬到第i层的方法,那么f[i] = f[i-1] + f[i-2] //第i层的方法数目等于第i-1层数目加上第i-2层数目。

初值:f[0] = 1, f[1] = 1。 //最开始没有爬和第一层的方法数目为1.

输出:f[n] 爬到第n层的方法数目。


实现方法两种:迭代法、递归法

递归法:时间复杂度:O(n) ,空间复杂度:O(n)

迭代法:时间复杂度:O(n),空间复杂度:O(1)


//递归法

class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        vector<int> ans(n+1);
        ans[0] = 1;
        ans[1] = 1;
        for(int i=2; i<=n; i++)
            ans[i] = ans[i-1] + ans[i-2];
        return ans[n];
    }
};

//迭代法

class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        // write your code here
        int prev = 0;
        int cur = 1;
        for(int i=1; i<=n; i++)
        {
            int tmp = cur;
            cur += prev;
            prev = tmp;
        }
        return cur;
    }
};



进阶:参考这里

主要是倒退一层,这个地方可能会违背动态规划无后效性的原则。 那么我们要怎么转化呢?
由条件:同一个位置不能重复走。我们可以知道如果要退步的话,不能退两层以上,因为用两步退两层再一步前进两层,那就会走相同的位置。所以我们最多只能退后一步。

那么题目的条件就可以转换两种情况,


a.跳两层(前进两层)。
b.退一层跳两层 (前进一层)。


1. 
State:

f[i][0] 表示最后一步是跳两层情况下爬到第i层的方法数目。

f[i][1] 表示最后是一步是退一层跳两层的情况下爬到第i层的方法数目。


2. Function:

 f[i+1][1] = f[i][0] 最后一步是退一层跳两层的情况下爬到第i+1层的方法数目 等于 从第i层情况a的数目跳两层退一层

这里不能考虑第i层的情况b的方法数,因为第i层情况b的数目是从第i+1层退一步得到的。


f[i+2][0] = f[i][0]+f[i][1] 最后一步是退一层跳两层的情况下爬到第i+2层的方法数目 等于 第i层所有情况跳两层

3. Intialize:

 f[0][0]=1初始化最开始没有爬的方法数目为1.


4. Answer: 

 f[n][0]+f[n][1] 爬到第n层a、b两种不同的方法的总和



相关文章

  • 本文总结一个目录提纲,只要是给自己看的,记录一下哪些东西已经总结过了. 闲谈IPv6-Loopback网口上的IPv6地址: https://blog.csdn.net/dog250/article/details/89333045 闲谈I ...

2020 jeepshoe.net webmaster#jeepshoe.net
13 q. 0.321 s.
京ICP备10005923号