帆软笔试 立方数

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;

public class CubeSumDP {

public static ArrayList<Integer> findCubes(int N) {
    int[] dp = new int[N + 1];
    int[] lastUsed = new int[N + 1]; // 用于追踪每个状态对应的立方数

    Arrays.fill(dp, Integer.MAX_VALUE);
    Arrays.fill(lastUsed, -1);

    dp[0] = 0; // base case

    // 预计算所有的立方数
    ArrayList<Integer> cubes = new ArrayList<>();
    for (int i = 1; i * i * i <= N; i++) {
        cubes.add(i * i * i);
    }

    // 动态规划填充dp数组
    for (int i = 1; i <= N; i++) {
        for (int cube : cubes) {
            if (cube > i) continue;
            if (dp[i] > dp[i - cube] + 1) {
                dp[i] = dp[i - cube] + 1;
                lastUsed[i] = cube;
            }
        }
    }

    // 重构解
    ArrayList<Integer> result = new ArrayList<>();
    int current = N;
    while (current > 0) {
        result.add((int)Math.cbrt(lastUsed[current]));
        current -= lastUsed[current];
    }
    Collections.sort(result,Collections.reverseOrder());
    return result;
}

public static void main(String[] args) {
    int N = 43;
    ArrayList<Integer> result = findCubes(N);
    System.out.println("结果: " + result);
}

}