一、题目

夏日炎炎，小男孩 Tony想买一些雪糕消消暑。

商店中新到 n支雪糕，用长度为 n的数组 costs表示雪糕的定价，其中 costs[i]表示第i支雪糕的现金价格。Tony一共有 coins现金可以用于消费，他想要买尽可能多的雪糕。

给你价格数组 costs和现金量 coins，请你计算并返回 Tony用 coins现金能够买到的雪糕的 最大数量 。

注意：Tony可以按任意顺序购买雪糕。

点击查看原题
难度级别： 中等

二、思路

1）01背包（二维内存太大，一维超时）

costs中代表了一只雪糕的价格，也就是其中每个元素不可重复选取，令dp[i][j]表示前i只雪糕花j金额可以购买的最大数量，状态转移方程如下：

由于当前状态只依赖于上一状态，可以将该状态方程压缩成一维

2）贪心

想要购买最多的雪糕，那么就会尽可能买价格较低的，将雪糕价格从低到高排列，先买便宜的雪糕，这样就可以计算处最大数量

三、代码

1）01背包（二维内存太大，一维超时）

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

时间复杂度为O(costs.length*coins)，空间复杂度为O(costs.length*coins)
优化为一维

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int[] dp = new int[coins + 1];
        for (int i = 0;  i < costs.length; i++) {
            for (int j = dp.length - 1; j > 0; j--) {
                if (costs[i] <= j) {
                    dp[j] = Math.max(dp[j], 1 + dp[j - costs[i]]);
                }
            }
        }
        return dp[coins];
    }
}

时间复杂度为O(coins)，空间复杂度为O(costs.length*coins)

2）贪心

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int count = 0;
        int ans = 0;
        for (int i = 0; i < costs.length; i++) {
            if (count + costs[i] <= coins) {
                count += costs[i];
                ans++;
            } else {
                break;
            }
        }
        return ans;
    }
}

n为costs长度，时间复杂度为O(logn)，空间复杂度为O(1)