題意：問在現有面值金額下 輸入一個m可以由多少種不同的金額組成

那么可以定義dp[i]表示i金額由多少種不同的金額組成方式

轉移方程：dp[i] = (dp[i] + dp[i-cost[j])%mod；
首先要定義dp[0] = 1；
然后枚舉面值 看不同數目下該面值可以組成那些金額
然后通過狀態轉移累計不同的組成方式

#include<bits/stdc++.h> using namespace std; int a[13] = {1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; const int mod = 1e9+7; int dp[100010]; int main() {int m;scanf("%d",&m);dp[0]=1;for(int i=0;i<13;i++){for(int j=a[i];j<=m;j++){if(dp[j-a[i]])dp[j] = (dp[j]+dp[j-a[i]])%mod; }}printf("%d\n",dp[m]);return 0; }

總結

以上是生活随笔為你收集整理的51nod 1101 换零钱 简单dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。