最少立方数之和

动态规划

表示能凑出的最少立方数，对于某个数，检查从1开始直到小于等于的立方数，有如下两种情况：

1. 如果，则，表示可以被一个凑出来。
2. 如果和都能被立方数凑出来，就进行状态转移：

base case：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = Integer.MAX_VALUE;
            for(int j = 1; j*j*j <= i; j++){
                if(j*j*j == i){
                    dp[i] = 1;
                }else if(dp[j*j*j] > 0 && dp[i - j*j*j] > 0){
                    dp[i] = Math.min(dp[i], dp[j*j*j] + dp[i - j*j*j]);
                }
            }
        }
        System.out.println(dp[n]);
    }
}

/*
动态规划，设dp[n]为组成 n需要的最少立方数个数
精髓所在：找的是所有差一步可以组成n的方案，求最小值加一；
dp[n] = 1 + min(dp[n-1],dp[n-8],dp[n-27],...) 要求n-i*i*i>=0
*/

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 0;dp[1] = 1;
        for(int i = 2;i<=n;i++){
            int min = Integer.MAX_VALUE;//用于保存最小的个数
            for(int j = 1;j*j*j<=i;j++){//找到最小的
                min = Math.min(min,dp[i-j*j*j]);
            }
            dp[i] = min + 1;
        }
        
        //
        System.out.println(dp[n]);
    }
}

	

import java.util.Scanner;

/*
 *
 * https://www.nowcoder.com/practice/4bc284dc9d0144628a722eb5d1191ef3?tpId=98&&tqId=32903&rp=7&ru=/activity/oj&qru=/ta/2019test/question-ranking
 *
 * */
public class Main {
    public static int solution(int dp[], int n) {
        if (n == 1) {
            return 1;
        }
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j * j <= i; j++) {
                if (min >= dp[i - j * j * j]) {
                    min = dp[i - j * j * j];
                }
            }
            dp[i] = min+1;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int[10000000];
        System.out.println(solution(dp, n));
    }
}

public class Test { public static void main(String[] args) {
        Random random = new Random();
        System.out.println(getInt(random.nextInt(1000000)));
    }  public static int getInt(int N){
        System.out.println("N = " + N);  int re = 0; int secondFor = 100;  for (int i = 1; i < 101; i++) {  for (int j = secondFor; j > 0; j--) {  if (j*j*j <= N){
                    N = N - j*j*j;
                    secondFor = j;
                    System.out.println("第" + i + "次做减法，j = " + j + "，j*j*j = " + j*j*j + "，N还剩：" + N );  break;
                }
           } if (N == 0){
                re = i;  break;
           }
        }  return re;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int temp = 1, preMin = Integer.MAX_VALUE;
            while (temp * temp * temp <= i) {
                preMin = Math.min(preMin, dp[i - temp * temp * temp]);
                temp++;
            }
            dp[i] = preMin + 1;
        }
        System.out.println(dp[n]);
    }
}