线性DP详细题解
2024-08-17 17:18:19
发布于:浙江
14阅读
0回复
0点赞
首先理解题目,我们知道这道题是线性DP的标准题。ok,
正解开始:
因为每次都要判断是不是要加1元,5元还是11元,我们先把所有数初始化为1,之后就是判断:(i>=5还是i>=11)
i>=5状态转移方程:min(dp[i],dp[i-5]+1) i>=11时:min(dp[i],dp[i-11]+1)。
这就是这题的解题思路。
上代码:
#include<bits/stdc++.h>
using namespace std;
int dp[100001];
int main() {
int n;
cin >> n;
dp[0] = 0; // 初始化dp[0]为0
for (int i = 1; i <= n; i++) {
dp[i] = i; // 初始化为i,表示用i个1元硬币
if (i >= 5) {
dp[i] = min(dp[i], dp[i - 5] + 1);
}
if (i >= 11) {
dp[i] = min(dp[i], dp[i - 11] + 1);
}
}
cout << dp[n] << endl;
return 0;
}
全部评论 1
求点赞
2024-08-17 来自 浙江
0
有帮助,赞一个