代码随想录 | Day34 | 动态规划 ：斐波那契数列&&爬楼梯

主要学习内容：

动规五部曲

509.斐波那契数列

509. 斐波那契数 - 力扣（LeetCode）

法1：dp

思路：

本题比较简单，因为初始化，数组含义，遍历顺序，递推公式全是确定的，直接看动规五部曲

1.确定dp数组以及下标的含义

就是题目中的F(n)，即前两个数字的加和

2.确定递推公式

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

3.dp数组如何初始化

1
dp[0]=0,dp[1]=1;

4.确定遍历顺序

求的是F(n)，即dp[n]，所以就是从0,1递推上来

5.举例推导dp数组

如果是3，F(3) = F(2) + F(1) = 1 + 1 = 2

如果是4，F(4) = F(3) + F(2) = 2 + 1 = 3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int fib(int n) {
        if(n<2)
            return n;
        vector<int> dp(n+1,0);
        dp[0]=0,dp[1]=1;
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
};

法2：递归

思路：

1.返回值和参数

返回值是int，因为我们要通过累加的方式得到F(n)，累加的结果靠返回值返回

1
int fib(int n)

2.终止条件

等于0那就返回0，等于1或2就是返回1

1
2
3
4
5
6
7
if(n==0)
	return 0;
if(n==2||n==1)
    return 1;
//或者
//if(n<2)
//	return n;也行

3.本层逻辑

f(n-1)由f(n-2)和f(n-3)相加得到

f(n-2)由f(n-3)和f(n-4)相加得到

树形结构其实是一颗二叉树，在叶子结点就是n=1或者n=2，就向上返回1，就相加上去了，直至f(n)

1
return fib(n-1)+fib(n-2);

完整代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if(n==2||n==1)
            return 1;
        return fib(n-1)+fib(n-2);
    }
};

70.爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

思路：

到达第n个台阶有几种方法呢?一开始不太好想

那就往前推，从n-1到达n有几种方法？ 一种，一次上一次台阶

从n-2到达n有几种方法？ 一种，一次上两次

为什么不能是一次上一个一共上两次？

因为你上一次是从n-2到n-1的台阶啦，已经把方法数包含在从n-1到n的里面啦

继续往前推的话

到达n-1有几种方法？

从n-2到n-1，一次上一个

从n-3到n-1，一次上两个

1.确定dp数组以及下标的含义

dp数组含义是登上第i个台阶由多少种方法

i下标就是第i个台阶

2.确定递推公式

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

3.dp数组如何初始化

1
dp[1]=1,dp[2]=2;

4.确定遍历顺序

求的是第n个台阶的总方法数，即dp[n]，所以就是从0,1递推上来

5.举例推导dp数组

到达2是 0-1-2 一种 0-2一种

到达3是 2-3 这是两种 1-3 这是一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        vector<int> dp(n+1,0);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

优化

因为每次递归只有i-1和i-2两个数，所以单独保存一下就行，然后就是两个交替赋值

a是dp[i-2]，b是dp[i-1]

a和b是台阶数差一的关系

sum是b的台阶数+1，所以在这一循环加完以后，b的值就是a下一循环的值，sum就是下一次b的值，两个都赋值就行。

因为从3开始的所以一共是加n-2次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        int a=1;
        int b=2;
        int sum=0;
        for(int i=3;i<=n;i++)
        {
            sum=a+b;
            a=b;
            b=sum;
        }
        return sum;
    }
};

递归会超时不多说了

1
2
3
4
5
6
7
8
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        return climbStairs(n-1)+climbStairs(n-2);
    }
};