algo-aha

整数分割就是完全背包问题，要分割的整数就是要恰好装满的背包容量。

背包问题的目标函数也不一定要求max，可以求min、求和、求积。

整数分割成一些数的和，并使它们的积最大

• https://leetcode.com/problems/integer-break/

int integerBreak(int n) {
    // 从[1..n-1]中取数，完全背包问题
    // n是背包容量，取的数i是物品体积，数i也是物品价值
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i < n; i++) {
        for (int v = i; v <= n; v++) { // 正序遍历各个容量
            dp[v] = max(dp[v], i * dp[v - i]);
        }
    }
    return dp[n];
}

整数分割成一些完全平方数的和，并使完全平方数个数最少

• https://leetcode.com/problems/perfect-squares/

int numSquares(int n) {
    // 设dp[i]表示和值i的最少完全平方数个数
    // dp[i] = min( dp[i-j*j]+1 /*分离出数j*/)，1<=j*j<=i
    // 初始dp[0]=0
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j*j] + 1);
        }
    }
    return dp[n];
}

整数有几种方式分割成连续数的和

• https://leetcode.com/problems/consecutive-numbers-sum/

只用一点数学

int consecutiveNumbersSum(int N) {
    // 假设N可分成k个连续数之和：N=x+(x+1)+(x+2)+...+(x+k-1)=kx+k(k-1)/2，
    // kx=N-k(k-1)/2，(N-k(k-1)/2)%k==0 (1)
    // x是>=1的整数，N-k(k-1)/2>=k，k(k+1)<=2N (2)
    int ans = 0;
    for (int k = 1; k * (k + 1) <= 2 * N; k++) {
        if ((N - k * (k - 1) / 2) % k == 0) ans++;
    }
    return ans;
}

整数分割为k个数，不考虑顺序，最大方案数

int divideNumber(int n, int k) {
	// 设dp[i][j]表示最大方案数，0<=i<=n, 0<=j<=k
	// 若j个数中至少有一个是1，方案数为 dp[i-1][j-1]
	// 若j个数中没有一个数是1，则所有j个数都减去1，方案数相同，为 dp[i-j][j]
	// 所以，dp[i][j] = dp[i-1][j-1] + dp[i-j][j]
	// 初始 dp[0][0] = 1，空方案
	// 若 i > j，dp[i][j] = 0
	const int MOD = 1e9 + 7;
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i >= j) {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % MOD;
			}
		}
	}
	return dp[n][k];
}