吃糖果
吃糖果
http://www.nowcoder.com/questionTerminal/72015680c32b449899e81f1470836097
思路
其实就是走楼梯问题，设 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;
if(n <= 2) cout << n << endl;
else {
for(int i = 3; i <= n; i ++){
int temp = dp1 + dp2;
dp1 = dp2;
dp2 = temp;
}
cout << dp2 << endl;
}
}
return 0;
} 算法题解 文章被收录于专栏
不定期更新一些算法题解，有什么问题可以随时留言~
查看3道真题和解析