分割整数

整数n分割成两个以上整数以达到某个目的（比如乘积最大，数量最少…）

思路：先拆出1个数来，剩下的不拆或者用dp数组得到最优值

下面以乘积最大为例

1
2
3
4
5
6
dp[]     数组保存满足题目要求的（乘积、数量...）
for(i:1~n)  遍历1到n的范围，每轮求出一个dp[i]的值供后面的使用
	best_var //保存每轮最优
	for(a:1~i)//先拆分出1个a，a遍历1~i
		best_var=max(a*(i-a),a*dp[i-a],best_var) //剩下的部分看是拆更优（使用dp得到），还是不拆更优，还是都不比前一轮更优
    dp[i]=best_var

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int integerBreak(int n) {
    int[]dp=new int[n+1];
    dp[1]=1;
    dp[2]=1;       
    for(int i=3;i<=n;i++){
        int maxi=0;
        for(int j=1;j<i;j++){
            int res=i-j;
            if(j<dp[j])continue;
            maxi=Math.max(Math.max(res*j,dp[res]*j),maxi);
        }
        dp[i]=maxi;         
    }
    return dp[n];
}

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numSquares(int n) {
    int []dp=new int[n+1];
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int maxi=(int)Math.sqrt(i);
        int minnum=i;
        for(int j=maxi;j>=1;j--){
            int res=i-j*j;
            minnum=Math.min(dp[res]+1,minnum);
        }
        dp[i]=minnum;
    }
    return dp[n];
}