文章
18
粉丝
183
获赞
57
访问
101.8k
非常经典的动态规划模板题
i颗糖的吃法=(这次吃1颗的吃法)+(这次吃2颗的吃法)
状态转移方程为:dp[i] = dp[i - 1] + dp[i - 2];
类似的题目还有:
代码如下:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int dp[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发