文章

18

粉丝

183

获赞

57

访问

101.8k

头像
1197 吃糖果 北京大学签到题
P1197 北京大学上机题
发布于2022年7月19日 10:59
阅读数 4.7k

非常经典的动态规划模板题

i颗糖的吃法=(这次吃1颗的吃法)+(这次吃2颗的吃法)

状态转移方程为:dp[i] = dp[i - 1] + dp[i - 2];

类似的题目还有:

  • 斐波那契数列
  • 爬楼梯(每次上1阶还是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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发