C语言刷题之动态规划入门(二)

本是古典何须时尚 2024-03-31 17:52 96阅读 0赞

**目录**

1.前言

2.斐波那契数列

1.题目

2.初步分析

3.代码实现

3.青蛙跳台阶

1.题目

2.初步分析

3.代码实现

4.青蛙跳台阶扩展问题

1.题目

2.初步分析

3.代码实现

--------------------

### 1.前言 ###

上期我们学习了动态规划基本概念和两道例题，对动态规划有了一定的了解。传送门：[C语言刷题之动态规划入门(一)][C]。

这期我们继续来学习动态规划的几道基础题，凡事都要循序渐进！

> 这几道题目分别是：斐波那契数列，青蛙跳台阶和青蛙跳台阶扩展问题

### 2.斐波那契数列 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
> 
> 斐波那契数列是一个满足
> 
> ![579aa0c0ded04656a4e845c478789f14.png][]
> 
> 的数列。
> 
> 数据范围：1≤n≤40
> 
> 要求：空间复杂度 O(n)，时间复杂度 O(n)
> 
> #### 输入描述： ####
> 
> 仅输入一个正整数 n。
> 
> #### 输出描述： ####
> 
> 输出斐波那契数列中第 n 个数。

--------------------

#### 2.初步分析 ####

斐波那契数列想必大家都不陌生，在学习递归的时候已经接触过了。但大家难免会发现，当n大于30时，程序运行的时间显然变长，这是由于递归多次遍历重复的子结点，时间复杂度O(F(n)) = O(2 ^n)，显然不符合题目的要求。因此我们可以采用动态规划的思想，避免重复计算，提高效率。

> **我的思路是**：创建一个一维数组dp，存放数列中的每个结点(元素),由关系式dp\[i\]=dp\[i-1\]+dp\[i-2\]最终可以即可得出斐波那契数列中的第n个数。由于我们事先将前置元素存储起来，下一次需要使用时就无需多次遍历，大大提升了效率，时间复杂度O(F(n)) = O(n)。主要代码如下：

--------------------

#### 3.代码实现 ####

//================递归写法=======================
    #include<stdio.h>
    int fun(int x)
    {
        if(x==1||x==2)
        {
            return 1;
        }
        else if(x>2)
        {
            return fun(x-1)+fun(x-2)
        }
    }
    int main()
    {
        int n=0;
        scanf("%d",&n);
        printf("%d",fun(n));
        return 0;
    }
    //================动态规划写法===================
    #include<stdio.h>
    int main() 
    {
    	int dp[40] = {0};
    	int n = 0;
        scanf("%d",&n);
        //对dp数组进行赋初值
    	dp[0] = 1;
    	dp[1] = 1;
    	for (int i = 2; i < n; i++)     //遍历dp数组
    	{
    		dp[i] = dp[i - 1] + dp[i - 2];
    	}
        printf("%d",dp[n-1]);
    	return 0;
    }

### 3.青蛙跳台阶 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
> 
> 数据范围：0≤n≤40
> 
> 要求：时间复杂度：O(n) ，空间复杂度： O(1)
> 
> #### 输入描述： ####
> 
> 本题输入仅一行，即一个整数 n
> 
> #### 输出描述： ####
> 
> 输出跳上 n 级台阶有多少种跳法

--------------------

#### 2.初步分析 ####

这题和前面的斐波那契数列基本上是一样的，不同的是，这里斐波那契数列的起始项是1,2,3,5,8，我们只需要将初值改一下即可。

> **需要注意的是：**本题的空间复杂度要求为O(1)，所以我们不能建立一个dp数组。通过上面我们可以看到斐波那契数列当前值只和dp数组的前两个值有关，再往前面的就无关了，所以我们没必要申请一个数组，直接使用两个变量进行存储即可，这样空间复杂度就满足要求了。

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    int main() {
    	int n = 0;
        scanf("%d",&n);
    	int f1=1,f2=2,f3=0;        //f1,f2为前两阶，f3为当前阶
    	for (int i = 2; i < n; i++)
    	{
    		f3 = f1  + f2 ;
            f1=f2;
            f2=f3;
    	}
        if(n==1)                   //第一阶
        {
            printf("%d",f1);
        }
        else if(n==2)              //第二阶
        {
            printf("%d",f2);
        }
        else                       //第n阶
        {
            printf("%d",f3);
        }
    	return 0;
    }

### 4.青蛙跳台阶扩展问题 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
> 
> 数据范围：1≤n≤20  
> 进阶：空间复杂度 O(1) ， 时间复杂度 O(1)
> 
> #### 输入描述： ####
> 
> 本题输入仅一行，即一个整数 n
> 
> #### 输出描述： ####
> 
> 输出跳上 n 级台阶的跳法

--------------------

#### 2.初步分析 ####

这里的青蛙比前面的青蛙更加厉害，他一次可以跳`1`阶，`2`阶，`3`阶`……,n阶`。所以要想跳到第`n`个台阶，我们可以从第`1`个台阶跳上来，也可以从第`2`个台阶跳上来……，所以递推公式是：

> f(n)=f(n-1)+f(n-2)+……+f(2)+f(1)

我们当然可以使用上面的方法建立一个dp数组，然后通过递推公式对dp数组进行赋值存储，采用动态规划的方式，这样的时间复杂度为O(F(n)) = O(n^2)，空间复杂度为O(F(n)) = O(n)，而题目要求空间复杂度 为O(1) ， 时间复杂度 为O(1)，所以显然会有一个公式可以直接解决这个问题。

> **我的思路是：**
> 
>  由递推公式我们可以得到以下两个公式
> 
>  **f(n)=f(n-1)+f(n-2)+ ……+f(2)+f(1)**
> 
>  **f(n-1)=f(n-2)+f(n-3)……+f(2)+f(1)**
> 
> 两式相减我们可以得到f(n)=2\*f(n-1)，而f(2)=2=2f(1),所以这其实是一个首项为 1，公比为2的等比数列，而我们通过等比数列的通项公式很快就可以求出第n项的值，此时空间复杂度为O(1) ， 时间复杂度为O(1)。主要代码如下：

--------------------

#### 3.代码实现 ####

#include <stdio.h>
    #include <math.h>
    int main()
     {
        int n=0,val=0;
        scanf("%d",&n);
        val=1*pow(2,n-1);   //等比数列通项公式
        printf("%d",val);
        return 0;
    }

--------------------

***以上，就是动态规划入门刷题(二)的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[C]: http://t.csdn.cn/YkDfn
[579aa0c0ded04656a4e845c478789f14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f03ef9b889664c8eba00c3225eaeb813.png