题解 | 硬币凑钱

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//对于n元 我们有三种硬币去凑齐 设dp[n]为凑出硬币数量最小值 假设我们已知dp[n-7],dp[n-5],dp[n-1]
	int n;//那么dp[n]的值其实就是在这三者中取最小值加一 因为只有这三种情况可以通过添加一枚硬币到达dp[n]
	cin >> n;
	vector<int>dp(n+1,0);
	dp[1]=1,dp[2]=2,dp[3]=3,dp[4]=4,dp[5]=1,dp[6]=2,dp[7]=1;
	for(int i=8;i<=n;i++)
	{
		dp[i]=min(min(dp[i-7],dp[i-5]),min(dp[i-5],dp[i-1]))+1;//状态转移方程
	}
	cout << dp[n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}