1833. Maximum Ice Cream Bars

給定預算及冰棒價格的情況下，找出可以買最多冰棒的數量。

其實這可以歸約為 0/1 knapsack 的問題，只是每枝的冰的價值都相等。用DP解此問題的時間複雜度是O(NW)，N為冰棒的數量，W為預算；而另一個解法 Greedy 是把冰棒價格由低排到高，每次都從最小的開始拿直到超出預算，而 Greedy 的時間複雜度為 O(NlogN + N)，及排序加上拿冰棒的時間。

為什麼我會提 Greedy ? 因為 Leetcode 給出的 case 在採用DP解法的時候反而會 Timeout，但Greedy不會，通常直覺DP的解法會比Greedy還要來的好，這讓我想到一個有趣的點。

在 Solution 有看到評論說，因為每枝冰棒的價值都是一樣的，所以用Greedy的解法會比較快。但為甚麼還有待探討

// Dynamic Programming
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        vector<unordered_map<int,int>> dp = vector<unordered_map<int,int>>(costs.size(), unordered_map<int,int>());
        return knapsack(dp, costs, costs.size()-1, coins);
    }
    int knapsack(vector<unordered_map<int,int>>& dp, vector<int>& costs, int item, int coins){
        if(coins < 0)
            return -1;
        if(item < 0 )
            return 0;
        
        if(dp[item][coins])
            return dp[item][coins];

        dp[item][coins] = max(
            knapsack(dp, costs, item-1, coins), 
            knapsack(dp, costs, item-1, coins-costs[item])+1
            );
        return dp[item][coins];
    }
};