貨幣系統
題目來源：usaco training 2.3
時間限制：1000ms 記憶體限制：64mb
題目描述
給定 \(V\) 種貨幣（單位：元），每種貨幣使用的次數不限，
不同種類的貨幣，面值可能是相同的，
現在，要你用這 \(V\) 種貨幣湊出 \(N\) 元錢，請問共有多少種不同的湊法，
輸入格式
第一行包含兩個整數 \(V\) 和 \(N\)，
接下來的若干行，將一共輸入 \(V\) 個整數，每個整數表示一種貨幣的面值，
輸出格式
輸出一個整數，表示所求總方案數，
資料范圍
\(1 ≤ V ≤ 25\) ,
\(1 ≤ N ≤ 10000\) ,
答案保證在 C/C++：long long Java：long 范圍內，
樣例輸入
3 10
1 2 5
樣例輸出
10
解題思路
解題代碼-Java
import java.util.*;
public class Main {
static long getPlanCount(int[] money, int n) {
int len = money.length;
long[][] dp = new long[len + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= len; i++) {
int vi = money[i - 1];
for (int j = 0; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= vi) {
dp[i][j] += dp[i][j - vi];
}
}
}
return dp[len][n];
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int v = input.nextInt();
int n = input.nextInt();
int[] money = new int[v];
for (int i = 0; i < v; i++) {
money[i] = input.nextInt();
}
input.close();
System.out.println(getPlanCount(money, n));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251498.html
標籤：其他
上一篇：位運算
下一篇：賬戶合并