Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
Giant high-frequency algorithm interview questions: “the currency issue series”, through the currency issue four combo, you will learn how to change from violent recursive dynamic programming, rather than come up to hard to suppress a dp, everything from trying to obtain, since violence recursive recursive filled dp grid through violence, look have further optimize the space, need not to need the slope optimization.
Currency problem I
Coins is an array of integers representing different denominations. And an integer amount representing the total amount.
Calculate and return the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1.
You can think of an infinite number of each coin.
Example 1:
Input: Coins = [1, 2, 5], amount = 11Copy the codeExample 2:
Input: Coins = [2], amount = 3 Output: -1Copy the codeExample 3:
Input: Coins = [1], amount = 0 Output: 0Copy the codeTip:
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 – 1
- 0 <= amount <= 10^4
leetcode
1, analysis,
Left-to-right trial model, try every currency, use 0 notes, use 1 note, use 2 notes… , and finally min is the minimum amount of currency that makes up AIM (amount)
2, implementation,
2.1 recursion of violence
Brute force implementation tests run out of time, but the idea is right and needs to be refined.
public static int coinChange(int[] coins, int amount) {
int ans = process(coins, 0, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// arr[index...] Denominations. You can choose from each denomination.
// Get the exact amount of rest, return the minimum number of cards
// Get the Integer.MAX_VALUE tag
private static int process(int[] arr, int index, int rest) {
// If rest is equal to 0, we don't need the currency
if (index == arr.length) { // base case
return rest == 0 ? 0 : Integer.MAX_VALUE;
}
int ans = Integer.MAX_VALUE;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
int next = process(arr, index + 1, rest - zhang * arr[index]);
if (next != Integer.MAX_VALUE) {
ans = Math.min(ans, zhang + next);
}
}
return ans;
}
Copy the code2.2 dp (fill in the form)
From violent recursion to dynamic programming, through recursive analysis, index position depends on index+1, so push from bottom to top and fill the grid
public static int coinChange(int[] coins, int amount) {
int ans = dp(coins, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int dp(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ans = Integer.MAX_VALUE;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
int next = dp[index + 1][rest - zhang * arr[index]];
if (next != Integer.MAX_VALUE) {
ans = Math.min(ans, zhang + next);
}
}
dp[index][rest] = ans;
}
}
return dp[0][aim];
}
Copy the code2.3 dp (Slope Optimization)
Dynamic programming with enumeration behavior can be further optimized by removing the innermost for loop and observing nearby positions to see which positions can replace enumeration behavior and make decisions in several finite positions. In DP, this operation can be considered as slope optimization.
public static int coinChange(int[] coins, int amount) {
int ans = dp(coins, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int dp(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - arr[index] >= 0&& dp[index][rest - arr[index]] ! = Integer.MAX_VALUE) { dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] +1); }}}return dp[0][aim];
}
Copy the codeCurrency issues II
You are given an integer array coins to indicate different denominations and an integer amount to indicate the total amount.
Please count and return the number of coin combinations that add up to the total. If no coin combination makes up the total, return 0.
Suppose there are an infinite number of coins of each denomination.
The problem data guarantees that the result is a 32-bit signed integer.
Example 1:
Enter: amount =5, coins = [1.2.5] output:4Explanation: There are four ways to add up the total:5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Copy the codeExample 2:
Enter: amount =3, coins = [2] output:0Explanation: denomination only2The coins don't add up to the total3 。
Copy the codeExample 3:
Enter: amount =10, coins = [10] output:1
Copy the codeTip:
- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000
- All values in coins are different
- 0 <= amount <= 5000
leetcode
1, analysis,
Try the model from left to right: 0 for each currency, 1 for each, and 2 for……
2, implementation,
2.1 recursion of violence
Brute force implementation tests run out of time, but the idea is right and needs to be refined.
public int change(int amount, int[] coins) {
return coinsWay(coins, amount);
}
public static int coinsWay(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return process(arr, 0, aim);
}
// arr[index....] All denominations, each denomination can choose any number of denominations, make up exactly this amount of money rest, how many ways?
private static int process(int[] arr, int index, int rest) {
if (index == arr.length) { // Base case there is no money
return rest == 0 ? 1 : 0;
}
int ways = 0;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
ways += process(arr, index + 1, rest - (zhang * arr[index]));
}
return ways;
}
Copy the code2.2 dp (fill in the form)
From violent recursion to dynamic programming, through recursive analysis, index position depends on index+1, so push from bottom to top and fill the grid
public int change(int amount, int[] coins) {
return dp(coins, amount);
}
public static int dp(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ways = 0;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
ways += dp[index + 1][rest - (zhang * arr[index])]; } dp[index][rest] = ways; }}return dp[0][aim];
}
Copy the code2.3 dp (Slope Optimization)
Finding enumeration behavior (innermost for loop) allows further slope optimization by looking at adjacent positions
public int change(int amount, int[] coins) {
return dp(coins, amount);
}
public static int dp(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - arr[index] >= 0) { dp[index][rest] += dp[index][rest - arr[index]]; }}}return dp[0][aim];
}
Copy the codeCurrency issues III
Arr is an array of currencies where the values are all positive. Let me give you a positive number, aim.
Each value is considered a piece of currency,
That there’s no difference between a currency with the same value,
Returns the number of methods that make up AIM
For example: ARR = {1,2,1,1,2,1}, AIM = 4
Methods: 1+1+1+1, 1+1+2, 2+2
There’s only 3 ways to do it, so return 3
1, analysis,
Currency problem II has an infinite number of coins, so this problem has a finite number of coins, that’s the key point
Count the number of times different denominations of currency appear
2, implementation,
2.1 recursion of violence
public static class Info {
public int[] coins; // Currency array
public int[] zhangs; // Count count group
public Info(int[] c, int[] z) { coins = c; zhangs = z; }}public static int coinsWay(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr); // Count tokens for different currencies
return process(info.coins, info.zhangs, 0, aim);
}
// An array of values of coins, positive and deduplicated
// zhangs The number of each denomination
private static int process(int[] coins, int[] zhangs, int index, int rest) {
if (index == coins.length) {
return rest == 0 ? 1 : 0;
}
int ways = 0;
for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
ways += process(coins, zhangs, index + 1, rest - (zhang * coins[index]));
}
return ways;
}
private static Info getInfo(int[] arr) {
// key: currency value, value: currency number
HashMap<Integer, Integer> counts = new HashMap<>();
for (int value : arr) {
if(! counts.containsKey(value)) { counts.put(value,1);
} else {
counts.put(value, counts.get(value) + 1); }}int N = counts.size();
int[] coins = new int[N];
int[] zhangs = new int[N];
int index = 0;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
coins[index] = entry.getKey();
zhangs[index++] = entry.getValue();
}
return new Info(coins, zhangs);
}
Copy the code2.2 dp (fill in the form)
Change dynamic programming based on violence recursion
public static int dp(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr);
int[] coins = info.coins;
int[] zhangs = info.zhangs;
int N = coins.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ways = 0;
for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
ways += dp[index + 1][rest - (zhang * coins[index])]; } dp[index][rest] = ways; }}return dp[0][aim];
}
Copy the code2.3 dp (Slope Optimization)
Find the inner for loop, draw a map to find the neighbor position, obtain the dependence relationship, further slope optimization, eliminate the inner for loop
public static int dp(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr);
int[] coins = info.coins;
int[] zhangs = info.zhangs;
int N = coins.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - coins[index] >= 0) {
dp[index][rest] += dp[index][rest - coins[index]];
}
if (rest - coins[index] * (zhangs[index] + 1) > =0) {
dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)]; }}}return dp[0][aim];
}
Copy the codeIV. Currency Issues
Arr is an array of currencies where the values are all positive. Let me give you a positive number, aim.
Each value is considered a piece of currency,
Even coins with the same value think each one is different,
Returns the number of methods that make up AIM
For example, arr = {1,1,1}, aim = 2
The 0th and the first can form a 2, the first and the second can form a 2, the 0th and the second can form a 2
There’s only 3 ways to do it, so return 3
1, analysis,
Currency problem III is that currencies of the same value do not differ in any way, while currencies of the same value are considered different, which is the key of this problem.
2, implementation,
2.1 recursion of violence
You solve it by force, and then you optimize it
Try the model from left to right: do you want each currency
public static int coinWays(int[] arr, int aim) {
return process(arr, 0, aim);
}
// arr[index....] There are several ways to make up exactly this amount of rest money
private static int process(int[] arr, int index, int rest) {
if (rest < 0) {
return 0;
}
if (index == arr.length) { // No more money!
return rest == 0 ? 1 : 0;
}
// Possibility 1: current currency
// Possibility 2: No current currency
return process(arr, index + 1, rest) + process(arr, index + 1, rest - arr[index]);
}
Copy the code2.2 dp (fill in the form)
According to the violent recursive dynamic programming, there is no enumeration behavior, and the optimal solution is to fill in the DP grid
Fill in the table: the index position depends on the index+1 position, so fill in from bottom up and left to right
public static int dp(int[] arr, int aim) {
if (aim == 0) {
return 1;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0); }}return dp[0][aim];
}
Copy the code