Knapsack problem - A

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> w;
    for (int i = 1; i * i * i <= n; ++i) {
        w.push_back(i * i * i);
    }

    int dp[n + 1] = {};
    for (int i = 0; i <= n; ++i) {
        dp[i] = i;
    }

    for (int x = 0; x <= n; ++x) {
        for (int i = 0; i < w.size(); ++i) {
            if (x + w[i] <= n && dp[x] + 1 < dp[x + w[i]]) {
                dp[x + w[i]] = dp[x] + 1;
            }
        }
    }

    cout << dp[n];
    return 0;
}