I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?
I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result[i], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.
Or maybe there was just a bug in my top down approach.
Update: The problem on LeetCode is: " You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
Example 2: coins = , amount = 3 return -1."
I defined an array result of size amount+1; result[i] is the minimum number of coins needed to reach amount i (with result = 0).
If we have N coins, and coin j has value V[j], the recursion is: result[i] = 1 + minimum of result[i-V[j]] for all j=1...N (only the j for which i-V[j]>=0)
I used a bottom up and top down approach to compute result[amount]:
If we don't have a coin of value 1, we won't need to compute result[i] for every i with a top down approach.
The time limit was exceeded for top down with this input: Coins: [186,419,83,408], Amount: 6249