# Bottom Up DP, C++, 112ms with explanation of recursive formula

• The intuition here is that to form a change for an amount (say X) and lets say we have coins of denomination {1, 2, 5}. We could have formed this change X from X-1 and then adding the coin of value 1 or from X-2 and adding a coin of value 2 or from X-5 and then adding the coin of value 5. Take a max over these to find the optimal solution. If coins is the vector/array of denominations of coins, more formally,

N = Number of elements in coins

OPT(x) = max(OPT(x - coins[k]) + 1) where k <- 0 to N

with base conditions,

OPT(0) = 0
OPT(x) = -1 if N == 0

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
if(n == 0) return -1;//cannot make change with 0 coins
if(amount == 0) return 0;//can always make change without any coins
int dp[amount+1];
dp[0] = 0;//base case: when amount = 0
for(int amt = 1; amt <= amount; amt++){
dp[amt] = -1;
for(int i = 0; i < n; i++){
if(amt - coins[i] >= 0 && dp[amt-coins[i]] != -1){
if(dp[amt] == -1) dp[amt] = dp[amt-coins[i]]+1;
else dp[amt] = min(dp[amt], dp[amt-coins[i]]+1);
}
}
}
return dp[amount];
}
};``````

• the number of each kind of coin is infinite, but it seems in your code that we have only one coin of each kind....

• Your question seems not clearly... The input is the kind of coin, and every kind of coin can be used many times. For example, dp[11]=min(-1, dp[11-1]+1, dp[11-2]+1, dp[11-5]+1)=min(-1, 2+1, 3+1, 2+1)=3. So what does your question mean?

• @1216114309zpf: it gets handled in the optimal substructure. Lets say we have coins of denomination {1, 2, 5} and we want to find change for 10. The optimal solution is to use 2 coins of denomination 5. So,

dp[5] would be 1 because we have a coin of value 5.
dp[10] would be dp[5] + 1 which is 2. (So, we used 2 coins of value 5)

• public static int coinChange(int[] coins, int amount){
int[][] grid=new int[coins.length+1][amount+1];
int m=0,n=0;
int temp=0;
for(int i=0; i<grid.length; i++){grid[i][0]=-1;}
for(int i=1; i<grid[0].length; i++){grid[0][i]=-1;}

``````    for(int i=1; i<grid.length; i++){
m=i;
for(int j=1; j<grid[i].length; j++){
n=j;
temp=j-coins[i-1];
if(temp==0){
grid[i][j]=1;
continue;}
if(temp<0){temp=0;}

if(grid[i-1][j]==-1 && grid[i][temp]==-1){
grid[i][j]=-1;
continue;
}
if(!(grid[i-1][j]==-1) && !(grid[i][temp]==-1)){
grid[i][j]=(grid[i-1][j]<(1+grid[i][temp]))?grid[i-1][j]:(1+grid[i][temp]);
continue;
}
if((grid[i-1][j]==-1) || (grid[i][temp]==-1)){
grid[i][j]=(grid[i-1][j]==-1)?(1+grid[i][temp]):grid[i-1][j];
continue;
}

}
}
System.out.println(n);
for(int i=0; i<=m; i++){
for(int j=0; j<=n; j++){
System.out.print(grid[i][j]+",");
}
System.out.println();
}
return grid[m][n];
}``````

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