爬楼梯
本帖最后由 bangbang-ande 于 2020-7-29 17:47 编辑题目是这样子的：
题目描述
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入输出样例
输入 #1
4
输出 #1
5
说明/提示
对于 60\%60% 的数据，N≤50；
对于 100\%100% 的数据，N≤5000。
然后写的代码是这样的：
#include <stdio.h>
int ans = 0;
int f(int n){
if(n == 1){
ans += 1;
return 0;
}
if(n == 2){
ans += 2;
return 0;
}
f(n - 1);
f(n - 2);
}
int main(){
int n;
scanf("%d", &n);
f(n);
printf("%d", ans);
}
可是运行起来是四个通过，剩下的超了时间（时间复杂度1s， 空间复杂度125mb）
然后又改了一下：
#include <stdio.h>
int ans = 0;
int f(int n){
if(n == 1 && n == 2){
ans += 1;
return 0;
}
f(n - 1);
f(n - 2);
}
int main(){
int n;
scanf("%d", &n);
f(n - 1);
printf("%d", ans);
}
结果空间复杂度又出问题。。。
请问还有没有更好的方法？
可以来下边那个网站测试
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
题目网站：https://www.luogu.com.cn/problem/P1255 public int climbStairs(int n) {
// base cases
if(n <= 0) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
int one_step_before = 2;
int two_steps_before = 1;
int all_ways = 0;
for(int i=2; i<n; i++){
all_ways = one_step_before + two_steps_before;
two_steps_before = one_step_before;
one_step_before = all_ways;
}
return all_ways;
} 你应该不是时间复杂度出问题，是最后忘了return了（结果报错了），还有你这个f函数不用返回值呀
#include <stdio.h>
int ans = 0;
void f(int n){
if(n == 1 && n == 2){
ans += 1;
return;
}
f(n - 1);
f(n - 2);
return;
}
int main(){
int n;
scanf("%d", &n);
f(n - 1);
printf("%d", ans);
} xiaosi4081 发表于 2020-7-29 13:46
你应该不是时间复杂度出问题，是最后忘了return了（结果报错了），还有你这个f函数不用返回值呀
但是还是不对啊 bangbang-ande 发表于 2020-7-29 15:11
但是还是不对啊
发错的内容（不要任何改动） 递归函数执行次数太多了，改成递推就好了
另外，头像好评
int climbStairs(int n){
int a=1, b=1;
for(int i = 1; i < n; i++)
{
b += a;
a = b - a;
}
return b;
} 有大佬告诉我60\%60%是什么意思吗？ 题目网站：https://www.luogu.com.cn/problem/P1255 Seawolf 发表于 2020-7-29 13:04
请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢! 风过无痕1989 发表于 2020-7-29 20:23
请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢!
是c程序
bangbang-ande 发表于 2020-7-29 20:31
是c程序
不是问你，你的程序当然是C程序啦 风过无痕1989 发表于 2020-7-29 20:23
请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢!
java 动态规划题目
leetcode测试通过
运行时间0 ms
内存消耗 5.2 MB
int climbStairs(int n)
{
int dp;
int i;
dp=0;
dp=1;
dp=2;
for(i=3;i<=n;i++)
{
dp=dp+dp;
}
return dp;
} SHRS23 发表于 2020-7-29 22:38
动态规划题目
leetcode测试通过
运行时间0 ms
你可不可以试试这个测试网站：
https://www.luogu.com.cn/problem/P1255 本帖最后由 Cool_Breeze 于 2020-7-30 13:55 编辑
#include <stdio.h>
#define size_t long long
int main()
{
size_t n=0;
scanf("%d",&n);
register size_t f1=1;
register size_t f2=1;
if (n == 1 || n == 2 || n == 3)
{
printf("%d", n);
return 0;
}
else
{
for(int i = 3;i < n;i++)
{
f1=f1+f2;
f2=f2+f1;
}
}
printf("%d", f1 + f2);
return 0;
} bangbang-ande 发表于 2020-7-29 23:18
你可不可以试试这个测试网站：
https://www.luogu.com.cn/problem/P1255
抱歉我没有洛谷账号{:10_266:} #include<stdio.h>
int climbStairs(int n)
{
long long dp;
int i;
dp=0;
dp=1;
dp=2;
for(i=3;i<=n;i++)
{
dp=dp+dp;
}
return dp;
}
int main()
{
int n = 0;
scanf("%d",&n);
printf("%ld", climbStairs(n));
return 0;
}
注册试了一下发现我竟然三年前注册过。。。
这是WA50的程序，不想改了，洛谷这数据大的离谱，我看题解大家都高精加法做的。。。
从我的力扣代码改的，这5000这种数据太大了，还得写个字符串表示大整数的加法，用动态规划从底层遍历到顶层结果就出来了
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<string> vec(5001, "0");
string addStrings(string num1, string num2) //字符串加法:"1"+"1"="2"
{
num1 = '0' + num1;
num2 = '0' + num2;
int len1 = num1.size();
int len2 = num2.size();
string ans = "";
int cry = 0;
len1--;
len2--;
char ch;
while (len1 != -1 && len2 != -1)
{
ch = num1 + num2 + cry - '0';
if (ch > '9')
{
ans = (char)(ch - 10) + ans;
cry = 1;
}
else
{
ans = ch + ans;
cry = 0;
}
len1--;
len2--;
}
if (len1 == -1)
while (len2 > -1)
{
ch = num2 + cry;
if (ch > '9')
{
ans = (char)(ch - 10) + ans;
cry = 1;
}
else
{
ans = ch + ans;
cry = 0;
}
len2--;
}
else
while (len1 > -1)
{
ch = num1 + cry;
if (ch > '9')
{
ans = (char)(ch - 10) + ans;
cry = 1;
}
else
{
ans = ch + ans;
cry = 0;
}
len1--;
}
if (ans == '0')
ans = ans.substr(1);
return ans;
}
stringclimbStairs(int n)
{
vec = "1";
vec = "2";
if (n == 1)
return "1";
if (n == 2)
return "2";
for (int i = 3; i <= n; i++)
vec = addStrings(vec, vec);
return vec;
}
int main()
{
ios::sync_with_stdio(false);
int num;
cin >> num;
string ans = climbStairs(num);
cout << ans;
return 0;
}
页:
[1]