题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
写了老半天，用的是完全背包的思路，后来发现先遍历背包和先遍历物品是完全不一样的两个东西。
题解给的是先遍历背包空间dp[n]，再遍历每个物品item，依次减去每个物品的值dp[n-item]，求出最小值
我用的是先遍历物品，不能拿之后的物品，通过二维数组转移的形式解题，发现自己麻烦很多，以后可能多多使用先遍历空间的思路。
import java.util.*;
public class Solution {
/**
* 最少货币数
* @param arr int整型一维数组 the array
* @param aim int整型 the target
* @return int整型
*/
public void print(int[][] dp){
for (int i = 0; i < dp.length; i++) { //this equals to the row in our matrix.
for (int j = 0; j < dp[i].length; j++) { //this equals to the column in each row.
System.out.print(dp[i][j] + " ");
}
System.out.println(); //change line on console as row comes to end in the matrix.
}
}
public int minMoney (int[] arr, int aim) {
// write code here
int[][] dp = new int[arr.length + 1][aim + 1];
for (int i = 0; i < arr.length + 1; i++) {
for (int j = 0; j < aim + 1; j++) {
if (j == 0) dp[i][j] = 0;
else dp[i][j] = 99;
}
}
for (int i = 1; i < arr.length + 1; i++) {
for (int j = 1; j < aim + 1; j++) {
if (j >= arr[i-1]) {
dp[i][j] = Math.min(dp[i][j - arr[i-1]] + 1, dp[i - 1][j]);
}
else dp[i][j] = dp[i - 1][j];
}
}
// print(dp);
if (dp[arr.length][aim] == 99) return -1;
else return dp[arr.length][aim];
}
}