题解 | #最少立方数之和#多重背包问题

取得可能所有的立方数，从1/8/27...作为背包 注意背包可以重复选择 dp数组可以初始化为INT_MAX，dp[0] = 0

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
    int N;
    while(cin >> N)
    {
        int count = 1, num = 1;
        vector<int> nums;
        while(num <= N)
        {
            nums.push_back(num);
            count++;
            num = pow(count,3);
            
        }
        vector<int> dp(N+1);
        for(int i = 0; i < count-1; i++)
        {
            for(int j = 1; j <= N; j++ )
            {
                if(j >= nums[i])
                {
                    if(dp[j] > 0)
                        dp[j] = min(dp[j],dp[j-nums[i]]+1);
                    else
                        dp[j] = dp[j-nums[i]]+1;
                }
            }
        }
        cout << dp[N] << endl;
        
    }
}