Leetcode的完美广场 [英] Perfect Square in Leetcode
问题描述
我无法理解Leetcode问题之一。
给出一个正整数n,找到最少的完美平方数(例如,例如,给定n = 12,则返回3,因为12 = 4 + 4 + 4;因此,得出n = 12,则返回3。给定n = 13,则返回2,因为13 = 4 + 9。
解决方案:
int numSquares(int n){
static vector< int> dp {0};
而(dp.size()< = n){
int m = dp.size(),平方= INT_MAX;
for(int i = 1; i * i <= m; ++ i)
squares = min(squares,dp [m-i * i] + 1);
dp.push_back(squares);
}
return dp [n];
}
我真的不明白 min(squares,dp [mi * i] +1)
。
thx。
您提到的解决方案,是该算法的自底向上版本。为了更好地理解该算法,我建议您看一下该解决方案的自上而下版本。
让我们仔细看看递归关系,以计算出 N
内包含的最小理想正方形数。对于给定的 N
和任意数字 x
(这是被视为是最短序列成员的候选)数字,其完美平方总和为 N
):
f如果N = 0,则(N,x)= 0;如果N> = x ^ 2,则
f(N,x)= min(f(N,x + 1),f(N-x ^ 2,1));
f(N,x)= + infinity,否则;
solution(N)= f(N,1)
现在,考虑到考虑到的重复发生,我们可以构建自顶向下的解决方案(我将用Java实现):
int解决(int n){
return resolve(n,1);
}
intsolve(int n,int curr){
if(n == 0){
返回0;
}
if((curr * curr)> n){
return POSITIVE_INFINITY;
}
//如果curr属于最短的数字序列,其完美平方之和为N
int inclusive = solve(n-(curr * curr),1)+ 1 ;
//否则:
int Exclusive = resolve(n,curr + 1);
返回Math.min(独占,含);
}
给定解决方案的运行时复杂度是指数级的。
但是,我们注意到只有 [1..n]
可能的值是<$ c $出现的c> n
和 [1..sqrt(n)]
值。这意味着只有 n * sqrt(n)
组合了函数 solve
的不同参数值组合。因此,我们可以创建备忘录表并降低自顶向下解决方案的复杂性:
int resolve(int n){
//初始化内存表
int [] [] memoized = new int [n + 1] [(int)(Math.sqrt(n)+ 1)]];
代表(int []行:已记录){
Arrays.fill(row,NOT_INITIALIZED);
}
return resolve(n,1,memoized);
}
intsolve(int n,int curr,int [] []记录){
if(n == 0){
返回0;
}
if((curr * curr)> n){
return POSITIVE_INFINITY;
}
if(memoized [n] [curr]!= NOT_INITIALIZED){
//子问题已解决
return memoized [n] [curr];
}
int独占= resolve(n,curr + 1,记录);
int inclusive = solve(n-(curr * curr),1,memoized)+ 1;
memoized [n] [curr] = Math.min(独占,含);
已记录的退货[n] [发生];
}
给出的解决方案的运行时复杂度 O(N * sqrt(N))
。
但是,可以将运行时复杂度降低到 O(N)
。
关于 f(N,x)
的递归关系仅取决于 f(N,x + 1)
和 f(N-x ^ 2,1)
-这意味着该关系可以等效转换到循环形式:
f(0)= 0
f(N)= min(f(N-x ^ 2)+ 1),在所有x上,这样x ^ 2 <= N
在这种情况下,我们仅需为 N
个自变量的不同值记住 f(N)
。
因此,下面提供了 O(N)
自上而下的解决方案:
int resolve_top_down_2(int n){
int [] memoized = new int [n + 1];
Arrays.fill(存储,NOT_INITIALIZED);
return resolve_top_down_2(n,记录);
}
intsolve_top_down_2(int n,int []记忆){
if(n == 0){
返回0;
}
if(memoized [n]!= NOT_INITIALIZED){
return memoized [n];
}
//如果1属于最短的数字序列,其完美平方之和为N
int结果= solve_top_down_2(n-(1 * 1)) + 1;
for(int curr = 2;(curr * curr)< = n; curr ++){
//检查是否有其他数字属于最短的数字序列,其完美平方加总到N
结果= Math.min(result,solve_top_down_2(n-(curr * curr))+ 1);记忆的
}
[n] =结果;
的返回结果;
}
最后,提出的自上而下的解决方案可以轻松地转化为自下而上的解决方案解决方案:
int resolve_bottom_up(int n){
int []记忆=新int [n + 1] ;
for(int i = 1; i <= n; i ++){
memoized [i] = memoized [i-(1 * 1)] + 1;
for(int curr = 2;(curr * curr)< = i; curr ++){
memoized [i] = Math.min(memoized [i],memoized [i-(curr * curr )] + 1);
}
}
已记录的退货[n];
}
I am having trouble understanding one of a Leetcode Problem.
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Solution:
int numSquares(int n) {
static vector<int> dp {0};
while (dp.size() <= n) {
int m = dp.size(), squares = INT_MAX;
for (int i=1; i*i<=m; ++i)
squares = min(squares, dp[m-i*i] + 1);
dp.push_back(squares);
}
return dp[n];
}
I really dont understand what is going on with min(squares,dp[m-i*i]+1)
. Can you please explain?
thx.
The solution, which you have mentioned, is the bottom-up version of the algorithm. In order to understand the algorithm better, I would advice to look at the top-down version of the solution.
Let's look closer at the recurrence relation for the calculation of the minimal amount of the perfect squares, contained inside the number N
. For given N
and any arbitrary number x
(which is the candidate for being considered as the member of the shortest sequence of numbers, whose perfect squares sums-up to N
):
f(N, x) = 0 , if N = 0 ;
f(N, x) = min( f(N, x + 1), f(N - x^2, 1) ) , if N >= x^2 ;
f(N, x) = +infinity , otherwise ;
solution(N) = f(N, 1)
Now, having in mind the considered recurrence, we can construct the top-down solution (I will implement it in Java):
int solve(int n) {
return solve(n, 1);
}
int solve(int n, int curr) {
if (n == 0) {
return 0;
}
if ((curr * curr) > n) {
return POSITIVE_INFINITY;
}
// if curr belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
int inclusive = solve(n - (curr * curr), 1) + 1;
// otherwise:
int exclusive = solve(n, curr + 1);
return Math.min(exclusive, inclusive);
}
The runtime complexity of the given solution is exponential.
However, we can notice that there are only [1..n]
possible values of n
and [1..sqrt(n)]
values of curr
. Which, implies, that there are only n * sqrt(n)
combinations of different values of arguments of the function solve
. Hence, we can create the memoization table and reduce the complexity of the top-down solution:
int solve(int n) {
// initialization of the memoization table
int[][] memoized = new int[n + 1][(int) (Math.sqrt(n) + 1)];
for (int[] row : memoized) {
Arrays.fill(row, NOT_INITIALIZED);
}
return solve(n, 1, memoized);
}
int solve(int n, int curr, int[][] memoized) {
if (n == 0) {
return 0;
}
if ((curr * curr) > n) {
return POSITIVE_INFINITY;
}
if (memoized[n][curr] != NOT_INITIALIZED) {
// the sub-problem has been already solved
return memoized[n][curr];
}
int exclusive = solve(n, curr + 1, memoized);
int inclusive = solve(n - (curr * curr), 1, memoized) + 1;
memoized[n][curr] = Math.min(exclusive, inclusive);
return memoized[n][curr];
}
Given solution has the runtime complexity O(N * sqrt(N))
.
However, it is possible to reduce the runtime complexity to O(N)
.
As far as the recurrence relation for f(N, x)
depends only on f(N, x + 1)
and f(N - x^2, 1)
- it means, that the relation can be equivalently transformed to the loop form:
f(0) = 0
f(N) = min( f(N - x^2) + 1 ) , across the all x, such that x^2 <= N
In this case we have to memoize the f(N)
only for N
different values of its argument.
Hence, below presented the O(N)
top-down solution:
int solve_top_down_2(int n) {
int[] memoized = new int[n + 1];
Arrays.fill(memoized, NOT_INITIALIZED);
return solve_top_down_2(n, memoized);
}
int solve_top_down_2(int n, int[] memoized) {
if (n == 0) {
return 0;
}
if (memoized[n] != NOT_INITIALIZED) {
return memoized[n];
}
// if 1 belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
int result = solve_top_down_2(n - (1 * 1)) + 1;
for (int curr = 2; (curr * curr) <= n; curr++) {
// check, whether some other number belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
result = Math.min(result, solve_top_down_2(n - (curr * curr)) + 1);
}
memoized[n] = result;
return result;
}
Finally, the presented top-down solution can be easily transformed to the bottom-up solution:
int solve_bottom_up(int n) {
int[] memoized = new int[n + 1];
for (int i = 1; i <= n; i++) {
memoized[i] = memoized[i - (1 * 1)] + 1;
for (int curr = 2; (curr * curr) <= i; curr++) {
memoized[i] = Math.min(memoized[i], memoized[i - (curr * curr)] + 1);
}
}
return memoized[n];
}
这篇关于Leetcode的完美广场的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!