jimore

用户名：uq_30465888842

访问量：9726

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	176
经　　验	6841
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：446

求一个很大的数的所有质因子（新方法）
浏览：246

佩尔方程——模板题
浏览：221

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

优质题解

DP解法（包含多种代码版本）

　　作者: jimore　　　　发表时间：2022-07-30 22:10:52 浏览：380　|　评论：0　

原题链接：教学楼的楼梯

## DP解法

**以后看到这种在某一个位置有多种走法，求到某一个位置的方案数，就可以用DP**
我们用 $$f(x)$$ 表示爬到第 $$x$$ 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
$$f(x) = f(x - 1) + f(x - 2)$$
$$f(x)=f(x−1)+f(x−2)$$

它意味着爬到第 $$x$$ 级台阶的方案数是爬到第 $$x - 1$$ 级台阶的方案数和爬到第 $$x - 2$$ 级台阶的方案数的和。很好理解，因为每次只能爬 $$1$$ 级或 $$2$$ 级，所以 $$f(x)$$ 只能从 $$f(x - 1)$$ 和 $$f(x - 2)$$ 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 $$0$$ 级开始爬的，所以从第 1 级爬到第 $$1$$ 级我们可以看作只有一种方案，即 $$f(1) = 1$$；从第 $$1$$ 级到第 $$2$$ 级也只有一种方案，即爬一级，$$f(2) = 1$$。这两个作为边界条件就可以继续向后推导出第 $$n$$ 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 $$f(3) = 2$$，$$f(4) = 3$$，$$f(5) = 5$$，……，我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 $$O(n)$$ 的实现，但是由于这里的 $$f(x)$$ 只和 $$f(x - 1)$$ 与 $$f(x - 2)$$ 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 $$O(1)$$。

在进行递推之前首先要对$$f$$进行初始化

f[1]=1; // 跳到1级有一种方案
    f[2]=1; // 跳到2级有一种方案

#### 2.完整代码

###### 2.1c++版本

#include <bits/stdc++.h>
    using namespace std;
    int t,n;
    int f[45]={0};
    int main(){
    	cin>>t;
    	while(t--){
    		cin>>n;
    		f[1]=f[2]=1;
    		for(int i=3;i<=n;i++){
    			f[i]=f[i-1]+f[i-2];
    		}
    		cout<<f[n]<<endl;
    	}
    	return 0;
    }

###### 2.2python版本

t=int(input())
    f=list(range(45))
    while t:
        n=int(input())
        f[1]=f[2]=1
        for i in range(3,n+1):
            f[i]=f[i-1]+f[i-2]
        print(f[n])
        t-=1

###### 2.3c版本

#include <stdio.h>
    int t,n;
    int f[45]={0};
    int main(){
    	cin>>t;
    	while(t--){
    		cin>>n;
    		f[1]=f[2]=1;
    		for(int i=3;i<=n;i++){
    			f[i]=f[i-1]+f[i-2];
    		}
    		cout<<f[n]<<endl;
    	}

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-求车速（C语言代码）

第一

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

DP解法（包含多种代码版本）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【出圈】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-数字母（C语言代码）

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言训练-求车速 （C语言代码）

第一

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

DP解法（包含多种代码版本）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【出圈】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-数字母 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-求车速（C语言代码）

　　评论区

【出圈】（C语言代码）

C语言训练-数字母（C语言代码）