首页 > 其他分享 >【力扣】数楼梯(动态规划)(看来高精度不学不行了)

【力扣】数楼梯(动态规划)(看来高精度不学不行了)

时间:2024-03-11 23:25:05浏览次数:24  
标签:return 走法 int 高精度 样例 long 力扣 楼梯 dp

问题描述

image

思路

这个递推公式并不难,n阶台阶的走法数目即为n-1阶的走法数目(再走一节就到了)加上n-2阶的走法数目。
当看到部分测试样例WA,而且都是靠后的测试样例而不是随机分散,那么有很大几率是数据类型存储有问题,存不了太大的数,而不是递推公式的问题。
想这题一样,当输入的N为500时,结果为:
image
。。。
就这样吧。。不搞竞赛的话应该也用不上

#include<bits/stdc++.h>
using namespace std;
long long countStairs(int N){
	if(N == 1){
		return 1;
	}
	if(N == 2){
		return 2;
	}
	
	vector<long long> 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];
}
int main(){
	int N;
	cin>>N;
	cout<<countStairs(N);
	return 0;
}

标签:return,走法,int,高精度,样例,long,力扣,楼梯,dp
From: https://www.cnblogs.com/satsuki26681534/p/18067340

相关文章

  • 746. 使用最小花费爬楼梯c
    intmin(inti,intj){if(i<j)returni;returnj;}intminCostClimbingStairs(int*cost,intcostSize){int*dp=(int*)malloc(sizeof(int)*(costSize+3));dp[0]=0;dp[1]=0;for(inti=2;i<=costSize;i++){dp[i]=min(dp[i-......
  • 力扣 22. 括号生成
    数字n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。示例1:输入:n=3输出:["((()))","(()())","(())()","()(())","()()()"]示例2:输入:n=1输出:["()"]classSolution{  publicList<String>generate......
  • 【力扣】排列问题(回溯法)
    问题描述排列问题的难点在于排列要求有序,并且在写的时候发现,如何在选择后面的元素后回过头去选择前面的元素,这是很难处理的,在前面的组合问题中,我们都是用startindex来处理,而在这里就行不通了。容易想到的一种解决方法就是另外设置一个与nums长度相同的used数组来记录元素的遍历......
  • 【力扣】非递减子序列
    题目代码如下:classSolution{public:vector<vector<int>>res;vector<int>path;booloccured(vector<int>&nums,intkey,intstartindex){for(inti=startindex;i<key;i++){if(nums[key]==nums[i]){......
  • 【力扣】子集II(回溯法)(排序函数的一种隐藏用法?)
    题目描述可以套回溯模版的题,但是在写的过程中发现,如果数组中有多个相同元素分散存在的话,就会有一些子集无法得到像这里的1,4,4,如果对数组从左到右枚举的话是无论如何都得不到的。对这样的数组使用排序函数后,造成的效果就是相同的元素都堆在了一起,这样就能正确地得到所有子集......
  • 【力扣】复原IP地址(回溯法)(分割问题)
    问题描述在这个题中,因为结果的数据类型为vector<string>所以直接在s中添加分割点比较方便,先看一下代码:classSolution{private:vector<string>result;//记录结果//startIndex:搜索的起始位置,pointNum:添加逗点的数量voidbacktracking(string&s,intst......
  • 力扣回溯之 39. 组合总和
    //剪枝优化classSolution{  publicList<List<Integer>>combinationSum(int[]candidates,inttarget){    List<List<Integer>>res=newArrayList<>();    List<Integer>path=newArrayList<>();    A......
  • 【力扣】组合总和3(组合的去重)
    问题描述注意,如果数组里有两个元素的值相同,那么这两个元素是可以出现在同一个组合里的:但是:如果按前面的思路分析的话,会发现结果中出现很多相同的组合。像这样:这很明显是由于两个相同的1造成的,因为当前的startindex对应第一个1时,向下一层递归后,starindex定位的还是1,。如......
  • 【力扣】组合总数(回溯法)
    题目描述#include<iostream>#include<vector>usingnamespacestd;vector<vector<int>>res;vector<int>path;intaccumulate(vector<int>path){ intsum; for(inti=0;i<path.size();i++){ sum+=path[i]; } r......
  • 【力扣】电话号码的组合(回溯法)
    问题描述classSolution{public:vector<string>res;stringpath;//charA[26]={'a','b','c','d','e','f','g',//'h','i','j','k&......