20200319递归和循环 剑指offer编程题整理 leetcode每日算法题

牛客网《剑指offer》 专题：

递归和循环	斐波那契数列	134918	30.49%
递归和循环	跳台阶	131877	35.02%
递归和循环	变态跳台阶	120854	40.31%
递归和循环	矩形覆盖	108415	34.55%

leetcode 70. 爬楼梯

官方解答 https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/

方法三：动态规划

算法

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

第 i 阶可以由以下两种方法得到：

1. 在第 (i-1) 阶后向上爬一阶。

2. 在第 (i-2)阶后向上爬 2 阶。

所以到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2)阶的方法数之和。

令 dp[i] 表示能到达第 i 阶的方法总数：

dp[i]=dp[i-1]+dp[i-2]

 

变态跳台阶链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?f=discussion
来源：牛客网

根据上一个题目：青蛙只跳1或2可以得出是一个斐波那契问题，即a[n]=a[n-1]+a[n-2],那么能跳1,2,3个台阶时a[n]=a[n-1]+a[n-2]+a[n-3],......

        依次类推，能推出本题的a[n]=a[n-1]+a[n-2]+......+a[1];由此得出代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public:     int jumpFloorII(int number) {         int *a=new int[number+1];         a[0]=1;         a[1]=1;         for(int i=2;i<=number;i++){             a[i]=0;             for(int j=i-1;j>=0;j--){                 a[i]+=a[j];             }         }         return a[number];     } };

但是上述代码时间复杂度达到O(n^2),空间复杂度也达到O(n),重新看一下上述结论：

a[n]=a[n-1]+a[n-2]+......+a[1];..........................①

a[n-1]=        a[n-2]+......+a[1];..........................②

两式相减可知：a[n]=2*a[n-1];

所以代码进一步简化：

1 2 3 4 5 6 7 8 9 10 11

class Solution { public:     int jumpFloorII(int number) {         int f=1,fn=1;         for(int i=2;i<=number;i++){             fn=2*f;             f=fn;         }         return fn;     } };

 矩形覆盖也是一个动态规划问题，把前一刻和前两刻的状态转化得到当前状态。

 

斐波那契序列被定义为

F0​=1，F1​=1，F1​=2，

Fn+2​=Fn+1​+Fn

斐波那契数列通项公式是怎样推导出来的？

https://www.zhihu.com/question/25217301

编程求斐波那契数列第n项可用递归法(指数复杂度)，循环法(线性复杂度)，矩阵法（对数复杂度）

https://blog.csdn.net/zhangmeimei_pku/article/details/79690438

矩阵法原理：

下面给出循环法(线性复杂度)代码

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

复杂度分析

• 时间复杂度：O(n)O(n)，单循环到 nn，需要计算第 nn 个斐波那契数。

• 空间复杂度：O(1)O(1)，使用常量级空间。