資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中硬幣找零 2
假設我們有不同面值的硬幣和一筆總金額。我們必須編寫一個模組來計算構成該金額的組合數。我們可以假設我們有每種硬幣無限多枚。因此，如果金額為 5，硬幣為 [1、2、5]，則有四種組合。(1+1+1+1+1)、(1+1+1+2)、(1+2+2)、(5)
為了解決這個問題，我們將遵循以下步驟 −
- 建立一個數組 dp，大小為金額 + 1
- dp[0] := 1
- n := 硬幣陣列的大小
- 對於範圍從 0 到 n – 1 的 i
- 對於範圍從硬幣[i] 到金額的 j
- dp[j] := dp[j – 硬幣[i]]
- 對於範圍從硬幣[i] 到金額的 j
- 返回 dp[金額]
示例(C++)
讓我們看看以下實現以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector <int> dp(amount + 1);
dp[0] = 1;
int n = coins.size();
for(int i = 0; i < n; i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
main(){
Solution ob;
vector<int> v = {1,2,5};
cout << (ob.change(5, v));
}輸入
5 [1,2,5]
輸出
4
更新於:2020 年 4 月 29 日
420 次瀏覽
廣告