首页 > 试题广场 >

最少立方数之和

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

热度指数：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

输入

输出

算法知识视频讲解

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)

Python

天天201905292018460

import math
n = int(input().strip())
k = math.floor(n**(1/3))
dp = [0] * (n+1)
dp[0] = 1
l1 = []
for i in range(1,k+1):
l1.append(i**3)
for m in range(1,n+1):
if m in l1:
dp[m]=1
else:
k1 = math.floor(m**(1/3))
l = []
for j in range(1,k1+1):
l.append(dp[m-j**3])
dp[m] = min(l)+1

print(dp[n])

我的复杂度过大吗？还能小吗

发表于 2019-08-07 20:19:03 回复(0)