P1197 吃糖果 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

我与代码的故事

2024年6月2日 13:23

吃糖果(和斐波那契数列递推差不多) 题解：

P1197

回复 0 | 赞 1 | 浏览 571

#include<bits/stdc++.h> using namespace std; typedef long long LL; int n; LL dp[30]; int main() { dp[1] = 1, dp[2] = 2; for(int i = 3; i <= 20; i ++) dp[i] = dp[i - 1] + dp[i - 2]; while(cin >> n) { cout << dp[n] <&...

2024年2月14日 10:43

吃糖果题解：

P1197

回复 1 | 赞 0 | 浏览 812

请问为什么我的做法哪里有问题呀 #include<iostream> using namespace std; int main() { int n; while (cin >> n) { long long int* a = new long long int[n]; a[1] = 1; ...

2024年3月19日 12:47

吃糖果题解：构建二叉树解决，二叉树的叶子结点个数就是方案个数

P1197

回复 0 | 赞 0 | 浏览 499

#include<bits/stdc++.h> using namespace std; typedef struct TNode { int val; struct TNode* rchild, * lchild; }*Tree; void BuildTree(Tree& t, int val) { if (val <0) return; t = new TNode; &nb...

2024年1月24日 17:33

吃糖果题解：动态规划

P1197

回复 0 | 赞 0 | 浏览 719

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

2023年8月5日 13:32

吃糖果题解：O(1)空间复杂度，内存140kb

P1197

回复 0 | 赞 0 | 浏览 738

#include<cstdio> int main() { int n; while(scanf("%d", &n) != EOF) { int f1 = 1, f2 = 2; for(int i = 2; i < n; i++){ int tmp = f1; f1 = f2; f2 += tmp; } if(n == 1) printf("%d\n", 1); else printf("%d\n", f2); } }

2023年5月17日 14:53

吃糖果题解：递推

P1197

回复 0 | 赞 0 | 浏览 1.2k

分析：该题的问题是问有多少种不同的吃完巧克力的方案，而不是需要多少天的问题，所以天数只起迷惑作用。我们假设盒内有1块巧克力，每次吃1或2块，求方法数；假设有2块巧克力，每次吃1或2块，求方法数；假设有3块巧克力，每次吃1或2块…类比下去会发现这个题就是走台阶问题（对于走台阶问题应该是比较熟悉的），巧克力数就是台阶数，每次能迈1或2阶。巧克力数方法数 1 1 2 2 3 3 4 &nb...

2023年3月28日 14:55

吃糖果方案，n个糖果可以一天吃1或2个，问有几种吃法

P1197

回复 0 | 赞 1 | 浏览 2.9k

#include <iostream> using namespace std; int Fib(int n){ if(n<=2) return n; return Fib(n-1)+Fib(n-2); } int main() { int n; while(cin>>n) cout<<Fib(n)<<endl; return 0; } 找规律发现：要看n个糖有几种吃法，假设n-1个糖有x1种吃法，n-2个糖有x2种吃法，那么n个糖就有x1+x2种吃法，因为吃了n-1块糖果之后只能选...

快乐小土狗

2023年2月8日 20:49

吃糖果动态规划

P1197

回复 0 | 赞 0 | 浏览 3.5k

思路其实就是走楼梯问题，设 dp[n] 为吃 n 块巧克力的方案，那要么最后剩两块一口气吃完或者最后剩一块一口气吃完，也就是 dp[n] = dp[n - 1] + dp[n - 2]，初始值 dp[1] = 1，dp[2] = 2，因为太简单我就直接写 O(1) 空间复杂度的解法了。 #include<iostream> using namespace std; int main(){ int n; while(cin >> n){ int dp1 = 1, dp2 = 2; ...

2022年7月19日 10:59

1197 吃糖果北京大学签到题

P1197

回复 0 | 赞 1 | 浏览 4.8k

非常经典的动态规划模板题 i颗糖的吃法=（这次吃1颗的吃法）+（这次吃2颗的吃法）状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2]; 类似的题目还有：斐波那契数列爬楼梯（每次上1阶还是2阶） ... 代码如下： #include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >...

2021年9月12日 10:06

对于先输入大n再输入小n，小n答案可以直接输出

P1197

回复 0 | 赞 0 | 浏览 5.9k

#include<stdio.h> int main() { int n, temp = 2; int a[20]; a[0] = 1; a[1] = 2; while(scanf("%d", &n) != EOF){ if(n <= temp) printf("%d\n", a[n ...

1
2

题目吃糖果

题解数量11

热门题解

1 吃糖果方案，n个糖果可以一天吃1或2个，问有几种吃法

2 吃糖果(和斐波那契数列递推差不多) 题解：

3 1197 吃糖果北京大学签到题

4 吃糖果题解：O(1)空间复杂度，内存140kb

5 吃糖果题解：动态规划

6 吃糖果动态规划

7 对于先输入大n再输入小n，小n答案可以直接输出

8 吃糖果题解：递推

9 吃糖果题解：构建二叉树解决，二叉树的叶子结点个数就是方案个数

10 吃糖果题解：