該樓層疑似違規已被系統折疊?隱藏此樓查看此樓

看著這代碼怎么這么熟悉。

package 動態規劃找零;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int change;

change = scan.nextInt();

int[] coins = {1, 5, 10, 21, 25};

int[] coinsUsed = new int[change];

int[] lastCoin = new int[change];

System.out.println(makeChange(coins, change, coinsUsed, lastCoin));

}

public static int makeChange(int[] coins, int maxChange, int[] coinsUsed, int[] lastCoin) {

coinsUsed[0] = 0;

lastCoin[0] = 1;

for (int cents = 1; cents <= maxChange; cents++) {

int minCoins = cents;

int newCoin = 1;

for (int j = 0; j < coins.length; j++) {

if (coins[j] > cents) {

continue;

}

if (coinsUsed[cents - coins[j]] + 1 < minCoins) {

minCoins = coinsUsed[cents - coins[j]] + 1;

newCoin = coins[j];

}

}

coinsUsed[cents] = minCoins;

lastCoin[cents] = newCoin;

}

return coinsUsed[maxChange];

}

}

weiss的書上的吧