小猴有 n颗糖果，每颗糖果的重量依次为 w 1 , w 2 , … , w n 小猴现在想要把这些糖果分成若干份分，要求每份糖果中不能有两颗糖果的重量相同。 请你帮助小猴计算，最少能分成多少份糖果。用C++,给出完整代码

这是一个经典的动态规划问题，可以使用哈希集合（HashSet）来解决。以下是用C++编写的解决方案：

#include <iostream>
#include <vector>
#include <unordered_set>

int minimumCut(vector<int>& weights) {
    int n = weights.size();
    if (n == 1) return 1; // 如果只有一个糖果，直接一份

    std::unordered_set<int> uniqueWeights;
    for (int i = 0; i < n; ++i) {
        uniqueWeights.insert(weights[i]);
    }

    int dp[uniqueWeights.size() + 1];
    dp[0] = 1; // 分成0份意味着不分
    for (int weight : uniqueWeights) {
        dp[1] = 1; // 至少需要1份包含该重量的糖果
        for (int k = 2; k <= n; ++k) {
            dp[k] = INT_MAX; // 初始化为最大值
            for (int j = 0; j < k - 1; ++j) {
                if (dp[j] != INT_MAX && !uniqueWeights.count(weights[j] + weight)) {
                    dp[k] = min(dp[k], dp[j] + 1);
                }
            }
        }
    }

    return dp[n];
}

int main() {
    std::vector<int> weights = {1, 2, 3, 4, 5};
    std::cout << "最少需要分成 " << minimumCut(weights) << " 份糖果。\n";
    return 0;
}

这个代码首先初始化了一个哈希集合存储所有的独特重量，然后通过动态规划计算将所有糖果分成每种独特重量所需最小份数。如果某个重量的组合已经存在于哈希集中，则不需要再次添加。