整数拆分

题目

具体思路

当前的结果取决于：将 n 怎么进行拆分，通过尝试可以发现，我们不能直接根据某种规律来得到一两种的划分方式，因此我们要遍历

1. 遍历当前能划分的所有方式 1 − n 2 种划分，一直划分到 n − 1 的话实际上是没有意义的，与前面相重复了。
2. res[n] 可以取得的最大效果实际上就是 ：1. 当前保存的最大值; 2. 当前进行拆分的结果 res[i] * (n - i) ; 3. 当前不进行差分得到的最终结果 i * (n – i)*

这里面的差分 res[i] 实际上包含了可能的所有种差分方式，因为 res[i] 实际上也是递归的进行差分的。

具体实现

class Solution {
    public int integerBreak(int n) {
        int[] res = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                res[i] = Math.max(Math.max(res[i - j] * j, (i - j) * j), res[i]);
            }
        }
        return res[n];
    }
}

// You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

// 2 :  1 1 = 1
// 3 :  1 2 = 2
// 4 :  2 2 = 4
// 5 :  3 2 = 6
// 6 :  3 3 = 9
// 7 :  3 4 = 12
// 8 :  3 3 2 = 18
// 9 :  3 3 3 = 27
// 10:  3 3 4 = 36

class Solution {
public:
    int integerBreak(int n) {
        // 1.定义dp数组，表示存放第i个整数的最大值
        vector<int> dp(n + 1, 0);
        // 3.初始化dp
        // dp[1] = 0;
        // 4.遍历一定是从前向后进行遍历
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // 2.定义状态转移方程
                temp = max(j * dp[i - j], j * (i - j));
                if (temp > dp[i])
                    dp[i] = temp;
            }
        }
        return dp[n];
    }
};