# DP approach O(nk), Also includes trace(though not required in the problem)

• I saw this really amazing video on this problem. Took most of the idea from that. The solution is very clean.

``````public class Solution {
public int coinChange(int[] coins, int amount) {
/*
This problem uses DP,
There are 2 arrays to be maintained
1. Minimum number of coins to reach a particular index value -- here we initialize the array size equal to amount + 1
2. From where the last move was played .. to trace (extra)
*/

int[] T = new int[amount + 1];
int[] R = new int[amount + 1];

// initialize
int len = T.length;

for (int i = 0; i < len; i++) {
T[i] = Integer.MAX_VALUE - 1;
R[i] = -1;
}

T[0] = 0; // To reach 0 no coins are required!

for (int j = 0; j < coins.length; j++) {
for (int i = 0; i < len; i++) {
if (i >= coins[j]) {
if (T[i] > 1 + T[i - coins[j]]) {
T[i] = 1 + T[i - coins[j]];
R[i] = j;
}
}
}
}

printTheTrace(R, coins);

if (T[amount] == Integer.MAX_VALUE - 1) {
return - 1;
} else {
return T[amount];
}

}

private void printTheTrace(int[] R, int[] coins) {
if (R[R.length - 1] == -1) {
System.out.println("The is no way we can get that!");
return;
}

int amount = R.length - 1;
while (amount != 0) {
int j = R[amount];
System.out.print(coins[j] + " ");
amount -= coins[j];
}
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.