咖啡馆为游客提供各种美味的甜点。甜点的编号从0到k-1。第i个甜点的成本是2个硬币,因为它是一个二进制咖啡馆!托马愿意花不超过n个硬币来品尝甜点。同时,他也没有兴趣购买任何甜品超过一次,因为一次就足以评价味道。 他可以用多少种不同的方式买几个甜点(可能是零个)来品尝 c++代码
时间: 2024-03-10 14:50:44 浏览: 18
以下是一种动态规划的解法,时间复杂度为O(kn):
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int k, n;
cin >> k >> n;
vector<int> cost(k);
for (int i = 0; i < k; i++) {
cost[i] = 2;
}
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
// dp[i][j]表示前i个甜点中花费不超过j个硬币的方案数
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
// 不选第i个甜点
dp[i][j] = dp[i - 1][j];
// 选第i个甜点
if (cost[i - 1] <= j) {
dp[i][j] += dp[i - 1][j - cost[i - 1]];
}
}
}
cout << dp[k][n] << endl;
return 0;
}
```
首先,我们用一个vector来记录每个甜点的成本。然后,定义一个二维数组dp,其中dp[i][j]表示前i个甜点中花费不超过j个硬币的方案数。
接下来,我们用两个循环来进行动态规划。对于第i个甜点,我们有两种选择:选或不选。如果不选第i个甜点,那么方案数就等于前i-1个甜点中花费不超过j个硬币的方案数,即dp[i-1][j]。如果选第i个甜点,那么方案数就等于前i-1个甜点中花费不超过j-cost[i-1]个硬币的方案数,即dp[i-1][j-cost[i-1]]。注意,这里的cost数组是从0开始的,所以要用cost[i-1]来表示第i个甜点的成本。
最后,输出dp[k][n]即为题目所求的答案。