思路
其实就是走楼梯问题,设 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; }