神奇的四次方数（洛谷P1679题题解，Java语言描述）

题目要求

P1679题目链接

分析

可以使用DP去做，当做“完全背包问题”问题来处理。

初值： f [ 0 ] = 0 f[0]=0 f[0]=0

c o s t [ ] cost[] cost[] ： c o s t [ i ] = i ∗ i ∗ i ∗ i cost[i] = i*i*i*i cost[i]=i∗i∗i∗i

状态转移方程： f [ j ] = M a t h . m i n ( f [ j ] , f [ j − c o s t [ i ] ] + 1 ) f[j] = Math.min(f[j], f[j-cost[i]]+1) f[j]=Math.min(f[j],f[j−cost[i]]+1)

AC代码（Java语言描述）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        int[] f = new int[num+1];
        Arrays.fill(f, (int)1e8);
        f[0] = 0;
        int limit = (int)Math.pow(num, 0.25);
        int[] cost = new int[limit+1];
        for (int i = 0; i