题解 | #吃糖果# 动态规划

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 30;
int dp[N][N], n; // dp[i][j]表示i个糖果吃j天的吃法数量

int main(){
	while( cin >> n ){
		dp[1][1] = 1;
		dp[2][1] = 1;
		dp[2][2] = 1;
		for(int i=3; i<n+1; i++)
			for(int j=(i+1)/2; j<=i; j++)
				dp[i][j] = dp[i-1][j-1] + dp[i-2][j-1];
			
		int res = 0;
		for(int j=0; j<=n; j++) res += dp[n][j];
		cout << res << endl;
	}
	
	return 0;
}