LeetCode 1798. 你能构造出连续值的最大数目（DP）

本文正在参与掘金团队号上线活动，点击查看大厂春招职位

题目描述

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以构造出 x 。

请返回从 0 开始（包括 0 ），你最多能构造出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：

0：什么都不取 []

1：取 [1]

从 0 开始，你可以构造出 2 个连续整数。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

好题。

首先我们可以总结下规律，一个数 x 只能由 <=x 的数字构成。如果 <=x 的数字集合没有构成 x 则不可能构成 x。

如果一些数字集合能够构成 [0, x]，再加上一个数字 y 则这些数字能够构成连续数字 [0, x + y]。

设 dp[i] 表示小于等于 i 的数字能构成的答案，cnt[i] 表示数字 i 出现的次数。

因为 >=i 的数字就不可能构成小于 i 的数字，所以要保证 dp[i-1]>=i-1 才可以继续向下求解。

递推公式

if (dp[i - 1] >= i - 1)
    dp[i] = dp[i - 1] + i * cnt[i];
复制代码

AC 代码

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        const int N = 40000;
        int dp[N + 5]; // dp[i] 表示小于等于i 的数字能构成的答案
        int cnt[N + 5];
        memset(cnt, 0, sizeof cnt);
        memset(dp, 0, sizeof dp);

        for (int x: coins) {
            cnt[x]++;
        }
        dp[0] = 0;
        for (int i = 1; i <= N; i++) {
            if (dp[i - 1] < i - 1) return dp[i - 1] + 1;
            
            dp[i] = dp[i - 1] + cnt[i] * i;
        }

        return dp[N] + 1;
    }
};
复制代码

当然，其实也不需要 dp 数组。

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        const int N = 40000;
        int cnt[N + 5];
        memset(cnt, 0, sizeof cnt);

        for (int x: coins) cnt[x]++;

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (ans < i - 1) {
                break;
            }
            ans = ans + cnt[i] * i;
        }

        return ans + 1;
    }
};
复制代码