Java DP O(m*n) Solution


  • 0
    F
    public class Solution {
        public int change(int amount, int[] coins) {
            if (coins == null) {
                return 0;
            }
            if (coins.length == 0 && amount == 0){
                return 1;
            }
            if (coins.length == 0) {
                return 0;
            }
            
            int size = coins.length;
            int[][] dp = new int[size][amount + 1];
            for (int i = 0; i < size; i++) {
                dp[i][0] = 1;
            }
            for (int j = 1; j < amount + 1; j++) {
                if (j % coins[0] == 0) {
                    dp[0][j] = 1;
                } else {
                    dp[0][j] = 0;
                }
                for (int i = 1; i < size; i++) {
                    if (coins[i] > j) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                    }
                }
            }
            return dp[size - 1][amount];
        }
    }
    

    use 1-D array

    public class Solution {
        public int change(int amount, int[] coins) {
            if (coins == null) {
                return 0;
            }
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 0; i < coins.length; i++) {
                for (int j = coins[i]; j < amount + 1; j++) {
                    dp[j] += dp[j - coins[i]];
                }
            }
            return dp[amount];
        }
    }
    

Log in to reply
 

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