题解 | #吃糖果#dp + bfs

本题可以使用动态规划dp加bfs实现，其实可以在草稿纸上罗列出情况，就可以发现出其中的规律了

动态规划dp

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int dp[N];

int convert(int n){
	if(n == 1)return 1;
	if(n == 2)return 2;
	
	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;
	
	while(cin >> n){
		cout << convert(n) << endl;
	}
	return 0;
}

bfs实现

#include <iostream>
#include <queue>

using namespace std;

int n;
int ans = 0;

int bfs(int n){
	if (n == 1) return 1;
    if (n == 2) return 2;
    
	queue<int> myqueue;
	myqueue.push(n);
	
	while(myqueue.size()){
		int current = myqueue.front();
		// 如果消耗完糖果了，方案加一 
		if(current == 0){
			ans ++; 
		}
		myqueue.pop();
		for(int i = 0;i < 2;i ++){
			int next = current;
			if(i == 0){
				next = next - 1;
			}else if(i == 1){
				next = next - 2;
			}
			if(next < 0){
				continue;
			}
			myqueue.push(next);
			
		}
	}
	return ans;
}


int main(){
	while(cin >> n){
		cout << bfs(n) << endl;
	}	
	return 0;
}