首页 > 试题广场 >

最少立方数之和

[编程题]最少立方数之和

热度指数：5339 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给出一个数字N（0<N<1000000）,将N写成立方数和的形式，求出需要的最少立方数个数。
例如N=17，1+8+8 = 17，最少需要3个立方数，则输出3。
N= 28,1+1+1+1+8+8+8=28, 需要7个立方数，1+27=28,需要2个立方数，所以最少立方数为2，则输出2。

输入描述:

一个数字N（0<N<1000000）

输出描述:

最少立方数个数

示例1

输入

输出

算法知识视频讲解

C/C++

ElonB

/*
动态规划，设dp[n]为组成 n需要的最少立方数个数
所有差一步可以组成n的方案，求最小值加一
dp[n] = 1 + min(dp[n-1],dp[n-8],dp[n-27],...) 要求n-i*i*i>=0
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, t, i;
    cin >> n;
    vector<int> dp(n + 1);
    dp[0] = 0;
    for(t = 1; t <= n; t++) {
        int t_min = INT_MAX;
        for(i = 1; i * i * i <= t; i++) {
            t_min = min(t_min, dp[t - i * i * i]);
        }
        dp[t] = t_min + 1;
    }
    cout << dp[n] << endl;
    return 0;
}

发表于 2019-07-13 13:58:21 回复(1)

keashem

前面说的dp方法挺不错，我提供一个贪心的反面方法，只能AC 50%，也就是每一次贪心都选择立方小于当前数的最大的数。比如145如果贪心选择的话为 145 = 125 + 8 + 8 + 1 + 1 + 1 + 1这样计数为7，但是145 可以划分成 145 = 64 + 27 + 27 + 27这种取下来是4。所以这里不能用贪心，要用dp来递推

编辑于 2019-08-09 21:18:15 回复(1)

Java

lmz9509

/*
动态规划，设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]);
    }
}

发表于 2020-04-27 12:36:28 回复(2)

Java

可以0613


	

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));
    }
}

发表于 2020-04-10 15:57:11 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    int num[100]={0},n,len=0;
    for(int i=1;i<100;i++)
        num[i]=i*i*i;
    cin>>n;
    while(num[len]<=n)
        len++;
    vector<int> dp(n+1,0);
    for(int j=0;j<=n;j++)
        dp[j]=j;
    for(int i=2;i<len;i++)
        for(int j=2;j<=n;j++)
            if(j>=num[i])
                dp[j]=min(dp[j],dp[j-num[i]]+1);
    cout<<dp[n];
    return 0;
}

编辑于 2019-11-11 10:37:48 回复(0)

向宇回桌

#include <bits/stdc++.h>
#define POW3(i) i*i*i
#define MAX 1000000 + 5
#define INT_MAX 0x3F3F3F3F
using namespace std;
int dp[MAX];

vector<int> pow3_list;

void init() {
    for (int i=1; POW3(i)<=MAX; i++) pow3_list.push_back(POW3(i));
    memset(dp, INT_MAX, sizeof(dp));
}

int main() {
    init();
    int n; cin >> n;
    dp[0] = 0;
    for (int i=1; i<=n; i++) {
        for (int j=0; pow3_list[j] <= i; j++) {
            dp[i] = min(dp[i], dp[i-pow3_list[j]] + 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

发表于 2019-09-10 21:55:29 回复(0)

精通Java外卖员

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		
		//把小于n的立方数装进集合
		ArrayList<Integer> al = new ArrayList<Integer>();
		for (int i = 1; i < 100; i++) {
			if(Math.pow(i, 3)>n) {
				break;
			}else if (Math.pow(i, 3)==n) {
				System.out.println(1);
				return;
			}else {
				al.add((int)Math.pow(i, 3));
			}
		}
		
		
		int sum = 0;
		dfs(n,sum,al,al.size()-1);
		System.out.println(min);
 	}

	private static void dfs(int n, int sum, ArrayList<Integer> al,int begin) {
		if(n==0) {//刚好够装，判定目前的总个数(sum)是否小于最小的，是的话min等于目前的sum
			if(sum<min) {
				min = sum;
			}
		}
		if(n<0||sum>min) {//n小于0，不够装  return    ||   使用次方数个数已经超过了目前最小的次方数    return
			return;
		}
		for (int i = begin; i >=0; i--) {
			dfs(n-al.get(i), sum+1, al, i);
		}
	}

}



//深搜解决一切问题。。。dp我太菜了总是理解不了

发表于 2019-08-25 13:14:06 回复(0)

随缘笔试

$N = a_1 \times 1^3 + a_2 \times 2^3 \times \cdots \times a_{t} \times t^3$

N视为背包，每件物品的重量是i,其对应的价值是

$a_i$

问题就是求解一个容量为N, 物品数为t的完全背包问题，并且要求背包一定要装满

$dp[i, j]= \min\{\sum a_i | \sum a_i \cdot i^3 = j \}$ $dp[i, j]= \min\{a_i + dp[i-1, j - a_i \cdot i ^ 3] | a_i \le \frac{j}{i^3} \}$

简化之，得

$dp[j]= \min\{1 + dp[j - i ^ 3] | i^3 \le j\}$

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int maxn = 1e6 + 20;
int dp[maxn];

int dp_solve(int n) {
    int t = (int)pow(n, 1/3.);
    for (int i = 1; i <= t; ++i) {
        for (int j = i * i * i; j <= n; ++j) {
            dp[j] = min(dp[j], 1 + dp[j - i * i * i]);
        }
    }
    printf("%d\n", dp[n]);
}

int main() {
    int n;
    scanf("%d", &n);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; ++i) dp[i] = INF;
    dp_solve(n);
    return 0;
}

发表于 2019-08-16 19:07:18 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            int x=1, Min=INT_MAX;
            while(x*x*x <= i){
                Min = min(Min, dp[i-x*x*x]);
                x++;
            }
            dp[i] = Min + 1;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

发表于 2019-07-11 21:11:38 回复(0)

Java

谁的电脑

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]);
    }
}

发表于 2019-07-08 16:06:45 回复(0)

Sshpark

BFS解决

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int solve(int n) {
    queue<pair<int, int> > q;
    q.push(make_pair(n, 0));

    vector<bool> vis(n+1, false);
    vis[n] = true;

    while(!q.empty()){
        int num = q.front().first;
        int step = q.front().second;
        q.pop();

        if (num == 0) return step;

        for (int i = 1; ; i++) {
            int a = num-i*i*i;
            if (a < 0) break;
            if (a == 0) return step+1;
            if (!vis[a]) {
                q.push(make_pair(a, step+1));
                vis[a] = true;
            }
        }
    }
    return 1;

}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    cout << solve(n) << endl;

    return 0;
}

发表于 2019-04-17 00:37:09 回复(0)

Java

pein531

动态规划

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

如果 $j^3=i$ ，则 $dp_i =1$ ，表示 $i$ 可以被一个 $j^3$ 凑出来。
如果 $dp_{j^3}$ 和 $dp_{i-j^3}$ 都能被立方数凑出来，就进行状态转移： $dp_i=min(dp_i,dp_{j^3}+dp_{i-j^3})$

base case： $dp_1=1$

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]);
    }
}

发表于 2022-01-11 10:26:03 回复(0)

Python3

牛客51833520号

n = int(input())
sum = 0
for i in range(100,0,-1):
if i^3 >n :
continue
elif i^3 <= n:
for j in range(7,0,-1):
if j*(i^3) <= n :
n = n-j*(i^3)
sum += j
break
else:
continue

print(sum)

这样为什么不对呢，求大神指点

发表于 2021-09-08 17:40:02 回复(0)

Java

科大15届软工代言人

亲测，java使用Math.pow(j, 3)函数会超时，j * j * j不会。

发表于 2021-08-25 18:35:00 回复(0)

小青年_

图片说明

package main

import (
    "fmt"
    "math"
)

func counter(num int) {
    var dp = make([]int, num + 1)
    dp[0] = 0
    dp[1] = 1

    var minInit = math.MaxInt64

    for i := 2; i <= num; i++ {
        var j int = 1
        var min int = minInit

        for j*j*j <= i {
            if dp[i-j*j*j] < min {
                min = dp[i-j*j*j]
            }
            j++
        }

        dp[i] = min + 1
    }

    fmt.Print(dp[num])
}

func main() {
    num := 0
    n, _ := fmt.Scan(&num)
    if n == 0 {
        fmt.Println(0)
    } else {
        fmt.Sprintf("%d", num)
        counter(num)
    }
}

发表于 2021-06-21 10:24:52 回复(0)

Python

muyuever

用的动态规划的思路解决的，自测调试可以22ms通过的，但是保存并调试时提示运行超时

total_num=int(input().strip())

min_num = [0]
for i in range(1, total_num + 1):
min_num.append(float('inf'))
for value in range(1,int(pow(total_num,1/3)+1)):
if value**3 <= i and min_num[i - value**3] + 1 < min_num[i]:
min_num[i] = min_num[i - value**3] + 1

print(min_num[-1])

发表于 2020-10-07 17:40:19 回复(0)

二手独轮车

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int>dp(n+1,INT_MAX);
    dp[0]=0,dp[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j*j*j<=i;j++){
            dp[i]=min(dp[i],dp[i-j*j*j]+1);
        }
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2020-04-15 14:24:49 回复(0)

良17

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 0;
        for (int i = 1;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] = 1 + min;
        }
        System.out.println(dp[n]);
    }
}

发表于 2020-04-11 16:37:20 回复(0)

Java

好大只的牛客

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;
    }
}

发表于 2020-03-27 10:26:50 回复(3)

野猪佩琪🐗

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[100];
        for(int i=1;i<100;i++)
            arr[i] = i*i*i;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=99;j>0;j--){
                if(i==arr[j]){
                    dp[i] = 1;
                    break;
                }else if(i>arr[j]){
                    int x = 1 + dp[i-arr[j]];
                    if(dp[i]==0)
                        dp[i] = x;
                    else
                        dp[i] = Math.min(dp[i],x);
                }
            }
        }
        System.out.println(dp[n]);
        
    }
    
}

发表于 2020-02-10 20:19:28 回复(0)

提交观点

问题信息

动态规划安卓工程师小米集团 2019 数学

来自：小米2019秋招安卓开...

上传者：小小

难度：

26条回答 41收藏 8238浏览

通过挑战的用户

查看代码

牛客67347...

2022-09-14 15:50:54
牛客45508...

2022-09-13 20:58:45
在写bug的加...

2022-09-13 19:53:07
culer0218

2022-09-13 19:17:06
哔哔波比波比

2022-09-13 12:50:02

最少立方数之和

输入描述:

输出描述:

输入

输出

动态规划

问题信息

热门推荐

通过挑战的用户

相关试题