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

这篇具有很好参考价值的文章主要介绍了[高精度加法与动态规划混合] 数楼梯。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数楼梯

题目描述

楼梯有 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 逆序,并转化为字符串返回。文章来源地址https://www.toymoban.com/news/detail-811348.html

具体的代码实现:
  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;
}

到了这里,关于[高精度加法与动态规划混合] 数楼梯的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • HJ57 高精度整数加法

    HJ57 高精度整数加法 1.逐位相加 按照传统加减法模式,从最后一位开始,逐位相加,逢十进一,传统方式从右往左相加,可以将数字翻转,变成从左往右按照数组遍历顺序相加,最后再将结果翻转。 时间复杂度:O(n+m) 2.利用大整形类型BigInteger实现

    2024年02月09日
    浏览(47)
  • 高精度加法,减法,乘法,除法(下)(C语言)

    前言 上一篇博客我们分享了高精度加法,减法,这一期我将为大家讲解高精度乘法和高精度除法。那让我们开始吧! 对加法和减法感兴趣的话就点我 让我们想想我们平时做数学时遇见乘法是怎么做的。以下图为例。 高精度乘法也是这样的一个思路,首先我们先把a和b的值储存

    2024年02月04日
    浏览(71)
  • 高精度加法,减法,乘法,除法(上)(C语言)

    前言 本篇内容介绍加法和减法,如果想看乘法和除法就点这里-高精度乘法,除法 加,减,乘,除这些运算我们自然信手捏来,就拿加法来说,我们要用c语言编程算a+b的和,只需让sum = a+b即可,可是这是局限的,我们都知道int的表示的最大值为2147483647(32位和64位机器)。但

    2024年02月03日
    浏览(44)
  • 算法笔记——高精度算法(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月08日
    浏览(74)
  • 【算法】模拟,高精度

      P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路就是模拟,值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存,因为如果是正着存的话,进位会有点trouble。 时间复杂度O(max(m,n))    P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (lu

    2024年02月09日
    浏览(53)
  • 高精度算法笔记·····························

    加法 减法 乘法 除法 高精度加法的步骤: 1.高精度数字利用字符串读入 2.把字符串 翻转 存入两个整型数组A、B 3.从低位到高位,逐位求和,进位,存余 4.把数组C从高位到低位依次输出         1.2为准备         3为加法具体实现(0按位取反为-1,即-1时结束等价于=0)  

    2024年01月21日
    浏览(60)
  • 高精度算法详解

    首先要知道为什么需要高精度算法: 高精度算法是 处理大数字 的数学计算方法,当数字过大不能用 int 和 long long 存储时,我们就可以 使用string和vector类型 来存储他们的每一位,然后进行计算。 我们可以先把要输入的两个数字放到vector中存储,注意要 反着存(后边做加法

    2024年01月17日
    浏览(61)
  • C++高精度算法

    目录 前言:  思路: 高精度加法: 高精度减法: 高精度乘法: 高精度除法:  代码: 一、高精度加法 二、高精度减法  三、高精度乘法  四、高精度除法 最后         计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特

    2024年02月14日
    浏览(54)
  • C++基础算法高精度篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了高精度算法的四种常用的计算 以下数字均指位数 ①A + B(精度均在10^6) ②A - B (精度均在10^6) ③A * b (len(A) = 10^6, a = 1000); ④A / b (len(A) = 10^6, a = 1000); Ⅲ. Ⅰ . A

    2024年02月16日
    浏览(36)
  • C++ 算法 高精度(较详细.)

            在我们进行计算的过程中,经常会遇到 几十位,甚至几百位的数字 的计算问题,也有可能会遇到小数点后几十位,几百位的情况,而我们面对这样的情况下,   和 的数据范围显然是 不够使用 的了。因此这时,我们就需要引入一个新的算法,叫做 高精度算法

    2023年04月10日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包