题解
2024-03-21 15:50:12
发布于:浙江
30阅读
0回复
0点赞
dp[i-1] 再拿 1 张 1 元钞票,则是 i 元,因此:dp[i] = dp[i-1] + 1;
dp[i-5] 再拿 1 张 5 元钞票,则是 i 元,因此:dp[i] = dp[i-5] + 1;
dp[i-11] 再拿 1 张 11 元钞票,则是 i 元,因此:dp[i] = dp[i-11] + 1;
题目要求最少的组合张数,所以只需要对 dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 取最小即可。
状态转移方程:dp[i] = min{ dp[i-1]+1, dp[i-2]+1, dp[i-11]+1 };
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int dp[N];
int main() {
int c[5] = {1, 5, 11} , m;
cin >> m ;
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 3 ; j++){
if (i >= c[j]) {
dp[i] = min((dp[i - c[j]] + 1) , dp[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
这里空空如也
有帮助,赞一个