帆軟筆試 立方數(shù)
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]; // 用于追蹤每個狀態(tài)對應(yīng)的立方數(shù)
Arrays.fill(dp, Integer.MAX_VALUE);
Arrays.fill(lastUsed, -1);
dp[0] = 0; // base case
// 預(yù)計算所有的立方數(shù)
ArrayList<Integer> cubes = new ArrayList<>();
for (int i = 1; i * i * i <= N; i++) {
cubes.add(i * i * i);
}
// 動態(tài)規(guī)劃填充dp數(shù)組
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;
}
}
}
// 重構(gòu)解
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("結(jié)果: " + result);
}
}
查看18道真題和解析
