t**r
发帖数: 3428 | 1 public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
++j;
}
dp[i] = min;
}
return dp[n];
} |
z**********e
发帖数: 91 | |
p**r
发帖数: 5853 | 3 1+n+1+n{1+1+log(n){1+1}+1}+1
~3+n+n{3+log(n+2)}
~n+n(3+log(n+2))
~n+n(log(n))
~O(nlogn)
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
++j;
}
dp[i] = min;
}
return dp[n];
}
【在 t**r 的大作中提到】
: public int numSquares(int n) {
: int[] dp = new int[n + 1];
: Arrays.fill(dp, Integer.MAX_VALUE);
: dp[0] = 0;
: for(int i = 1; i <= n; ++i) {
: int min = Integer.MAX_VALUE;
: int j = 1;
: while(i - j*j >= 0) {
: min = Math.min(min, dp[i - j*j] + 1);
: ++j;
|
S********t
发帖数: 3431 | 4 where does the log() come frome?
【在 p**r 的大作中提到】
: 1+n+1+n{1+1+log(n){1+1}+1}+1
: ~3+n+n{3+log(n+2)}
: ~n+n(3+log(n+2))
: ~n+n(log(n))
: ~O(nlogn)
:
: public int numSquares(int n) {
: int[] dp = new int[n + 1];
: Arrays.fill(dp, Integer.MAX_VALUE);
: dp[0] = 0;
|
p**r
发帖数: 5853 | 5 while(i-j*j>=0)
【在 S********t 的大作中提到】
: where does the log() come frome?
|
S********t
发帖数: 3431 | 6 think twice...
【在 p**r 的大作中提到】
: while(i-j*j>=0)
|
p**r
发帖数: 5853 | 7 for worst scenario:i=n
i-j*j>=0,
same as i>=j*j
same as j<=log(n) because i=n
【在 S********t 的大作中提到】
: think twice...
|
t**r
发帖数: 3428 | |
|
p**2
发帖数: 613 | 9 光觉得有啥用，你把推导过程写出来，我看看是不是O（n）
【在 t**r 的大作中提到】
: 为啥我觉得是amortized o(n)
|
S********t
发帖数: 3431 | 10
=================================
=================================
i>=j^2 <==> j<=i^0.5
【在 p**r 的大作中提到】
: for worst scenario:i=n
: i-j*j>=0,
: same as i>=j*j
: same as j<=log(n) because i=n
|
S********t
发帖数: 3431 | 11 http://math.stackexchange.com/questions/1241864/sum-of-square-r
For a quick conclusion, see the third answer about harmonic numbers
【在 t**r 的大作中提到】
: 为啥我觉得是amortized o(n)
|
p**2
发帖数: 613 | 12 i^0.5不就是log(i),算法中计算复杂度log以2为默认底...
【在 S********t 的大作中提到】
: http://math.stackexchange.com/questions/1241864/sum-of-square-r
: For a quick conclusion, see the third answer about harmonic numbers
|
D*********S
发帖数: 21 | 13 神逻辑。。。
你的数学老师当年也教体育吧？
【在 p**2 的大作中提到】
: i^0.5不就是log(i),算法中计算复杂度log以2为默认底...
|
p**2
发帖数: 613 | 14 哈哈哈哈，我数学是体育老师教的，
不好意思，不知道当时怎么就僵掉了，确实应该是N^3/2
【在 D*********S 的大作中提到】
: 神逻辑。。。
: 你的数学老师当年也教体育吧？
|
