7-lines Simple Java DP Solution


  • 1
    C
    public class Solution {
        public int change(int amount, int[] coins) {
            int[][] dp=new int[coins.length+1][amount+1];
            dp[0][0]=1;
            for (int i=1;i<=coins.length;i++)
                for (int j=0;j<=amount;j++)
                    for (int k=0;k<=(coins[i-1]==0?0:j/coins[i-1]);k++) // for test case 0, [0]
                        dp[i][j]+=dp[i-1][j-k*coins[i-1]];
            return dp[coins.length][amount];
        }
    }
    

    By the way, 1 <= coin <= 5000, but one of the test cases:

    0
    [0]
    

    I think this should be fixed. @viacheslav


  • 0
    L

    Brilliant solution!
    By the way, I think space complexity can be O(m) instead of O(mn).


  • 0
    Z

    @ckcz123 Hi! My approach is the same. How about time complexity?


  • 0
    V

    @ckcz123 Thank you! Fixed.


  • 0
    M

    Can you provide some explanation of your solution ?


  • 0
    R

    Can you explain your code?


  • 1
    V

    More standard solution is just based on the simple recursive formula:

    F(n, S) = F(n, S - coins[n-1]) + F(n-1, S) for n > 0, S > 0

    Corner cases:
    F(n, 0) = 1
    F(n, S) = 0 for S < 0
    F(n, S) = 0 for n <= 0, S > 0

    Then a possible implementation is just two nested for-loops:

    • outer loop runs over the number of coins n (0 <= n <= coins.length),
    • inner loop runs over all the possible S (0 <= S <= amount).

    In this implementation, dp[n][S] represents F(n, S), where we save the values of F.

    This implementation uses different and more complicated recursive function. Let's try to obtain it from the definition of F(n, S). Let's apply this function multiple times:

    • firstly, for F(n, S),
    • then for F(n, S - cost[n-1]),
    • then for F(n, S - 2 cost[n-1]),
      and so on, till we get:
    • F(n, S - k cost[n-1])
      for some maximum k such that S - k cost[n-1] is still >= 0, or
      0 <= k <= S / cost[n-1]

    So basically, we expand F(n, S) many times by applying the recursive function for F:

    F(n, S) = F(n, S - coins[n-1]) + F(n-1, S)
    = F(n, S - 2 coins[n-1]) + F(n-1, S - coins[n-1]) + F(n-1, S)
    = F(n, S - 3 coins[n-1]) + F(n-1, S - 2 coins[n-1]) + F(n-1, S - coins[n-1]) + F(n-1, S)
    ...
    = F(n-1, S - k coins[n-1]) + ... + F(n-1, S - 2 coins[n-1]) + F(n-1, S - coins[n-1]) + F(n-1, S)
    = sum( F(n-1, S - k coins[n-1]), for 0 <= k <= S / cost[n-1] )

    So algebraically the initial simple recursive function and the last recursive function with the sum are equal, but the former is simpler and runs faster (using DP, its time complexity is just O(coins.length * amount)), while the later is more complicated and runs slower (using DP, it is O(coins.length * amount^2) -- 3 nested loops).

    You may ask: "What is the reason to make things more complicated?"

    Usually there are no so many ones, but may be in this case the author came up directly to the more complicated recursive function and just implemented it without trying to find better solution. In some cases, if there is a simpler solution, one can algebraically transform it to a simple one. This is true for this case as well, having the last recursion, we can apply some transformation and find the simple solution.

    May be the author was aware of other solutions but just wanted to share his unique implementation. Anyway I find this approach is not less interesting than others.


  • 0
    V

    @mdwadhwani and @richa1112, I tried to explain the idea, let me know if it helps.


  • 1
    V

    Actually, the recursive function

    F(n, S) = sum( F(n-1, S - k coins[n-1]), for 0 <= k <= S / cost[n-1] )

    could be easily obtained from the following idea:

    • if we do not pick the coin (n-1) at all, the number of combinations equal to F(n-1, S);
    • if we pick the coin (n-1) only once, the number of combinations equal to F(n-1, S - cost[n-1]);
    • if we pick the coin (n-1) exactly twice, the number of combinations equal to F(n-1, S - 2 cost[n-1]);

    and so on.

    • if we pick exactly k coins (all of them are the same, with value coins[n-1]), the number of combinations equal to F(n-1, S - k cost[n-1])

    The number of combinations for the problem of (n, S) is equal to the sum of all the cases above.


Log in to reply
 

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