Wanna Cube Up?

Dynamic programming solution: Use the recurrence $f(n, s) = \sum_{k=0}^9 f(n-1, s-k^3),$ where $f(n,s)$ is the number of $n$ -digit numbers whose sum of the cubes of their digits is $s$ , with initial values $f(1,k^3)=1$ for $k=0,\ldots,9$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <cstdio>
#include <cmath>
#define ll long long
#define N 18
using namespace std;


ll memo[N+1][729*N+1];

void init() {
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= 729*N; j++) {
            memo[0][0] = 0;
        }
    }
    for(int i = 0; i <= 9; i++) {
        memo[1][i*i*i] = 1;
    }
    for(int i = 2; i <= N; i++) {
        for(int j = 0; j <= 729*i; j++) {
            ll sum = 0;
            for(int k = 0; k <= 9; k++) {
                if(j-k*k*k >= 0) sum += memo[i-1][j-k*k*k];
            }
            memo[i][j] = sum;
        }
    }
}

int main() {
    init();
    ll tot = 0;
    for(int i = 1; i <= 9*cbrt(N); i++) {
        tot += (memo[N][i*i*i]-memo[N-1][i*i*i]);
    }
    printf("%lld\n", tot);
    return 0;
}

Just as the problem square up, but with slightly larger numbers. Dynamic programming on the state (current sum, numbers remaining), can be memoized for a total of ~250,000 unique states.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <bitset>
#include <map>

using namespace std;

bitset<14000> cube;
map< pair<int, int>, long long> memo;

long long num_cubes(int current_sum, int numbers_remaining) {
    if (numbers_remaining == 0) {
        return cube[current_sum];
    }
    if (memo.find(make_pair(current_sum, numbers_remaining)) != memo.end())
        return memo[make_pair(current_sum, numbers_remaining)];

    long long ans = 0;
    for (int i = 0; i < 10; i++) {
        ans += num_cubes(current_sum + i*i*i, numbers_remaining - 1);
    }
    return memo[make_pair(current_sum, numbers_remaining)] = ans;
}

int main() {
    int i = 1;
    while (i*i*i < 14000) {
        cube[i*i*i] = true;
        i++;
    }
    long long ans1 = 0;
    for (int i = 1; i < 10; i++) {
        ans1 += num_cubes(i*i*i, 17);
    }
    cout << ans1 << endl;
}