2024.6.15

2024.6.15 【夜幽幽，月优优，曲悠悠，吾忧忧。】

Saturday 五月初十

---

<theme = oi-“DP”>

看几道DP基础题，

巩固一下DP思路和基础

Coin Combinations I

//2024.6.15
//by white_ice
//Coin Combinations I CSES - 1635 
#include<bits/stdc++.h>
#include"fopen.cpp"
using namespace std;
#define itn long long 
#define int long long 
constexpr int oo = 102;
constexpr int mod = 1000000007;
constexpr int op = 1000006;int n,m;
itn st[oo];itn f[op];signed main(){fre();ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m ;for (itn i=1;i<=n;i++)cin >> st[i];f[0] = 1;for (itn i=1;i<=m;i++){for (itn j=1;j<=n;j++){if (i-st[j]>=0){f[i] += f[i-st[j]];}} f[i] %= mod;}cout << f[m];return 0;
}

依次遍历每一个总价值i如果比硬币价值大，

就加上f[i-c[j]]种方式

Coin Combinations II

//2024.6.15
//by white_ice
//Coin Combinations II CSES - 1636
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define itn int
constexpr int oo = 102;
constexpr int op = 1000006;
constexpr int mod = 1000000007;itn n,x;
itn st[oo];itn f[op];signed main(){//fre();ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> x;for (itn i=1;i<=n;i++)cin >> st[i];f[0] = 1;for (itn i=1;i<=n;i++){for (int j=st[i];j<=x;j++){f[j] += f[j-st[i]];f[j] %= mod;}}cout << f[x];return 0;
}

从枚举每个硬币的价值开始，

加上从此硬币能到的总价值中差的价值的组成方式

（有点绕

注意以上两种题的区别，

有序和无序的DP写法中主要就是遍历顺序的改变

Minimizing Coins

//2024.6.15
//by white_ice
//Minimizing Coins CSES - 1634
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define itn int
constexpr int oo = 102;
constexpr int op = 1000006;itn n,m;
itn c[oo];  int f[op];signed main(){//fre();ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m;memset(f,0x3f3f3f3f,sizeof(f));for (itn i=1;i<=n;i++)cin >> c[i];sort(c+1,c+n+1);f[0] = 0;for (int i=1;i<=m;i++){for (int j=1;j<=n;j++){if (i<c[j])break;f[i] = min(f[i],f[i-c[j]]+1);}}cout << (f[m]==0x3f3f3f3f?-1:f[m]);return 0;
}

依旧是枚举每个硬币的价值

取当前硬币以外组成的最小方式比较。