[高精度加法与动态规划混合] 数楼梯

2023-12-21 20:34:57

数楼梯

题目描述

楼梯有 N N N 阶,上楼可以一步上一阶,也可以一步上二阶。

编一个程序,计算共有多少种不同的走法。

输入格式

一个数字,楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

5000

样例输出 #1

6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626

提示

  • 对于 60 % 60\% 60% 的数据, N ≤ 50 N \leq 50 N50
  • 对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 5000 1 \le N \leq 5000 1N5000

解题分析

注意到本题数据十分十分的大,即使是long long int都没办法存储,考虑将高精度加法与之混合。
对于这个数楼梯的问题,其实是很经典的动态规划问题,到达第n个台阶的方法数会等于到达n-1个台阶的方法数加上到达n-2个台阶的方法数。

f[n]=f[n-1]+f[n-2]

十分清晰,接下来就是考虑利用高精度加法进行计算即可。

主要使用了动态规划和大数加法两种算法去解决这个上楼梯的问题。以下是详细的解析:

动态规划算法:

动态规划是这里的主要算法,用于解决上楼梯的问题。对于 n 阶楼梯,设 f(n) 为走到第 n 阶楼的方法数量,那么 f(n) 可以分解为:

  1. 从第 n-1 阶上一步走到第 n 阶,这种方法有 f(n-1) 种
  2. 从第 n-2 阶上两步走到第 n 阶,这种方法有 f(n-2) 种

所以,f(n) = f(n-1) + f(n-2)。这就是动态规划的状态转移方程。

我们知道,当 n=1 或 n=0 时,f(n) 都等于 1 (只有一种上法),所以这是递归的基准条件。

大数加法算法:

由于题目中 n 可能最大为 5000,通过上面的递推关系不难看出,结果可能会超过程序中基本数据类型的范围,这时我们可以使用大数加法来储存和计算具有大量数字的整数。

具体来说,大数加法先将两个大数字符串逆序并转化为整数,然后从低位到高位依次相加。如果某位相加的结果大于等于10,则需要进位。这在代码中体现为:

  1. num3[i]=num1[i]+num2[i];——当前位的加法
  2. num1[i+1]+=num3[i]/10; ——向高位的进位处理
  3. num3[i]%=10; ——保留当前位的余数

最后,将计算出的结果数组 num3 逆序,并转化为字符串返回。

具体的代码实现:
  1. 设置大数动态规划数组 num dp[5005];
  2. 复制初始值到第0阶和第1阶,表示没有楼梯和有一阶楼梯时的走法数目都是1.
  3. 遍历动态规划数组 dp,用 add(dp[i-1].number, dp[i-2].number) 计算 dp[i]。
  4. 最后输出 dp[N].number,这就是走上N阶楼梯的全部方法数。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
struct num{
	char number[5005];
};

num dp[5005];
int num1[5005],num2[5005],num3[5005];
char result[5005];

char *add(char *number1,char *number2){
	int len1=strlen(number1),len2=strlen(number2);
	int len=max(len1,len2);
	memset(num1,0,sizeof(num1));
	memset(num2,0,sizeof(num2));
	memset(num3,0,sizeof(num3));
	memset(result,0,sizeof(result));
	for(int i=0,j=len1-1;i<len1;i++,j--){
		num1[i]=number1[j]-'0';
	}
	for(int i=0,j=len2-1;i<len2;i++,j--){
		num2[i]=number2[j]-'0';
	}
	for(int i=0;i<=len;i++){
		num3[i]=num1[i]+num2[i];
		num1[i+1]+=num3[i]/10;
		num3[i]%=10;
	}
	int k=0,l=0;
	for(l=5004;l>=0;l--){
		if(num3[l]){
			break;
		}
	}
	for(;l>=0;l--){
		result[k++]=num3[l]+'0';
	}
	result[k]='\0';
	return result;
}

int main(){
	int N; cin>>N;
	strcpy(dp[0].number,"1");
	strcpy(dp[1].number,"1");
	for(int i=2;i<=N;i++){
		strncpy(dp[i].number,add(dp[i-1].number,dp[i-2].number),5000);
	}
	printf("%s",dp[N].number);
	return 0;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135139227
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。