1575. [算法课动态规划] 换硬币

include

include

using namespace std;

/* 开辟f[28]数组,其中f[x]代表组合成x所用的最少硬币; 看最优策略的最后一步f[27],最后一枚硬币可能是2,5,7, 分别对应f[25]+1,f[22]+1,f[20]+1;最后一步的最优策略肯定是这三种种最少的一个, 假设是f[25],则继续向前判断倒数第二枚硬币也可能是2,5,7又分别对应f[23]+1,f[20]+1,f[18]+1,继续循环

*/ int f[100];//1确定状态; const int inf=10000000; int main(){

int n; cin>>n; int a[3]={2,5,7}; f[0]=0; for(int i=1;i<=n;i++){//(4)计算顺序 f[i]=inf;//(3)初始化条件; for(int j=0;j<3;j++){//f[i]=min(f[i-2]+1,f[i-5]+1,f[i-7]+1) if(i>=a[j]&&f[i-a[j]]!=inf) {//(3)边界条件 f[i]=min(f[i-a[j]]+1,f[i]);//(2)状态方程 } } } if(f[n]!=inf) cout<<f[n]<<endl; else cout<<"-1";

}