279. 完全平方数【中等】
题解和昨天的322. 零钱兑换对比一下
发现几乎完全一样，只是多了一步计算完全平方数，代码完全可以照搬
class Solution {
private int[] square;
public int numSquares(int n) {
//生成完全平方数数组
int slen=(int)Math.sqrt(n);
square=new int[slen];
judgeSquares(n);
int[] dp=new int[n+1];
Arrays.fill(dp,n+1);
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j
if(i>=square[j])
dp[i]=Math.min(dp[i],dp[i-square[j]]+1);
}
}
return dp[n];
}
//筛选出完全平方数
public void judgeSquares(int n){
for(int i=0;i<(int)Math.sqrt(n);i++){
square[i]=(i+1)*(i+1);
}
}
}
简化一下代码，发现其实完全平方数数组并不需要，用
j
∗
j
(
0
<
j
<
=
n
)
j*j (0 顺便说一下，乘法比开方的效率高，因此最好用 j*j 时间复杂度：
O
(
n
n
)
O(nsqrt{n})
O(nn
) 空间复杂度：
O
(
n
)
O(n)
O(n) 343. 整数拆分【中等】 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) 空间复杂度：
O
(
n
)
O(n)
O(n) 377. 组合总和 Ⅳ【中等】 和 518. 零钱兑换 II 简直一模一样…不知道说啥了，直接默认代码就得了 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) 空间复杂度：
O
(
n
)
O(n)
O(n) 题解中有个大佬总结了类似的背包问题的模板，希望用一种规律搞定背包问题，太牛了，非常精辟！学习！class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];
dp[0]=0;
//金额
for(int i=1;i<=n;i++){
dp[i]=n+1;
//硬币
for(int j=1;j*j<=i;j++){
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
（2）i-j继续拆：乘积为
j
∗
d
p
[
i
−
j
]
j*dp[i-j]
j∗dp[i−j]
所以dp[i]=Math.max( i*(i-j) , i*dp[i-j] )class Solution {
public int integerBreak(int n) {
int[] dp=new int[n+1];
for(int i=2;i<=n;i++){
for(int j=1;j
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp=new int[target+1];
dp[0]=1;
for(int i=1;i<=target;i++){
for(int j=0;j
