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


  • 5
    H

    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];
        }
    };

  • 0
    1

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


  • 0

    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?


  • 0
    H

    @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)


  • 0
    S

    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];
    }

Log in to reply
 

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