首页 > 试题广场 >

最少立方数之和

[编程题]最少立方数之和
  • 热度指数：5390 时间限制：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

输入

28

输出

2
算法知识视频讲解
添加回答
keashem头像 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头像 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头像 可以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外卖员头像 精通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)
C/C++
nbgao头像 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头像 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)
C/C++
ElonB头像 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)
随缘笔试头像 随缘笔试

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

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

简化之，得

#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)
Java
pein531头像 pein531

动态规划

dp_n表示能凑出n的最少立方数，对于某个数，检查从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]);
    }
}

发表于 2022-01-11 10:26:03 回复(0)
C++
牛客187183257号头像 牛客187183257号 
#include <iostream>
using namespace std;
int getlf(int a)
{
    return a*a*a;
}
int main() {
    int n;cin>>n;
    int count[1000010] = {0};
    count[1] = 1;
    for(int i= 2;i<1000010;i++)
    {
        int tmpmin = 1000000000;
        int index = 1;
        while(i-getlf(index)>=0)
        {
            tmpmin = min(tmpmin,count[i-getlf(index)]);
            index++;
        }
        count[i] = tmpmin+1;
    }
    cout<<count[n];
}

发表于 2025-03-23 18:26:55 回复(0)
Python3
牛客51833520号头像 牛客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届软工代言人头像 科大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头像 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头像 良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)
提交观点

问题信息

动态规划 安卓工程师 小米集团 2019 数学
来自：小米2019秋招安卓开...
上传者：小小
难度：
27条回答 10517浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最少立方数之和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号