C++程序最小乘积子集

前言

在学习算法和数据结构的过程中，经常会遇到一些经典问题，最小乘积子集就是其中一个值得深入研究的问题。

问题描述

问题描述：给定一个正整数数组，找出其子集的最小乘积，要求子集中元素个数不小于2。

例如，对于数组{2, 3, 4}，其所有子集为{2}{3}{4}{2,3}{2,4}{3,4}{2,3,4}，其中最小的乘积对应的子集为{2,3}，其乘积为6。

思路分析

暴力枚举

对于每一个子集，计算其乘积并更新最小乘积，但这种方法时间复杂度为 $O(2^n)$ ，无法处理规模较大的数组。

int minProduct(vector<int>& nums) {
    int n = nums.size();
    int res = INT_MAX;
    for(int i = 0; i < (1<<n); i++) {
        int product = 1;
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            if(i & (1<<j)) {
                product *= nums[j];
                cnt++;
            }
        }
        if(cnt >= 2) res = min(res, product);
    }
    return res;
}

动态规划

设 $dp[i]$ 为包含第 $i$ 个元素的子集的最小乘积，可以得到如下转移方程：

$dp[i] = \min(dp[i], \min(dp[j]\times\prod_{k=j+1}^i nums[k]));\quad i>j$

其中， $nums[i]$ 表示数组中的第 $i$ 个元素。使用 $O(n^2)$ 的时间复杂度，可通过时间复杂度。

int minProduct(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    int res = INT_MAX;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(j == 0) dp[i] = min(dp[i], nums[i]*nums[j]);
            else dp[i] = min(dp[i], dp[j-1]*nums[i]*nums[j]);
        }
        res = min(res, dp[i]);
    }
    return res;
}

优化动态规划

$O(n^2)$ 的时间复杂度不能满足要求，因此需要进一步优化。考虑到当前状态仅与上一个状态有关，可以使用滚动数组降为 $O(n)$ 的时间复杂度。

int minProduct(vector<int>& nums) {
    int n = nums.size();
    int res = INT_MAX;
    int dp[n];
    fill(dp, dp+n, INT_MAX);
    for(int i = 0; i < n; i++) {
        for(int j = i-1; j >= 0; j--) {
            if(j == 0) dp[j] = min(dp[j], nums[i]*nums[j]);
            else dp[j] = min(dp[j], dp[j-1]*nums[i]*nums[j]);
            res = min(res, dp[j]);
        }
        dp[i] = nums[i];
        res = min(res, dp[i]);
    }
    return res;
}