java数据结构与算法刷题-----LeetCode343. 整数拆分（TODO）

很多人觉得动态规划很难，但它就是固定套路而已。其实动态规划只不过是将多余的步骤，提前放到dp数组中（就是一个数组，只不过大家都叫它dp），达到空间换时间的效果。它仅仅只是一种优化思路，因此它目前的境地和线性代数一样----虚假的难。

1. 想想线性代数，在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时，完全摸不着头脑，一上来就是行列式和矩阵，根本不知道这玩意是干嘛的。
2. 线性代数从根本上是在空间上研究向量，抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
3. 反观国内的教材，直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候，只会觉得一知半解，觉得麻烦，完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候，发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材，什么狗东西（以上是自己学完线性代数后的吐槽，我们同学无一例外都这么觉得）。

而我想告诉你，动态规划和线性代数一样，我学完了才知道，它不过就是研究空间换时间，提前将固定的重复操作规划到dp数组中，而不用暴力求解，从而让效率极大提升。

1. 但是网上教动态规划的兄弟们，你直接给一个动态方程是怎么回事？和线性代数，一上来就教行列式和矩阵一样，纯属恶心人。我差不多做了30多道动态规划题目，才理解，动态方程只是一个步骤而已，而这已经浪费我很长时间了，我每道题都一知半解不理解，过程及其痛苦。最后只能重新做。
2. 动态规划，一定是优先考虑重复操作与dp数组之间的关系，搞清楚后，再提出动态方程。而你们前面步骤省略了不讲，一上来给个方程，不是纯属扯淡吗？
3. 我推荐研究动态规划题目，按5个步骤，从上到下依次来分析

1. DP数组及下标含义
2. 递推公式
3. dp数组初始化
4. 数组遍历顺序（双重循环及以上时，才考虑）
5. dp数组打印，分析思路是否正确（相当于做完题，检查一下）

方法一：时间复杂度O($n^2$),空间复杂度O(n)

1. 这种解法的思路，就是用dp数组保存小于等于目标值n的，每一个正整数值i，将i依次看做要拆分的数，找出它们每一个的最大乘积情况。最终递推到目标值n.
2. 上面解析过程中，频繁出现i = j+(i-j) 和 i = j+dp[i-j]。这个初学者会很难理解。

1. i是我们当前要拆分的数，j是我们这次拆分必须有的数，比如i=10代表我们要拆分10这个数，试图找到它的最大乘积。而我们先从j=1开始枚举，也就是这次拆分，必须拆出一个1，剩下的你随便。再比如j=3时，就是我们这次必须先拆出来一个3，剩下的7你随便怎么拆。
2. 而如果我们只想拆成2个数，比如10 = 1 + 9. i = 10. 而j = 1就表示我们这次拆出来的两个数里面，其中一个必须是1. 剩下一个数是多少呢？不就是10-1 ==> i-j = 9吗。这就有了10 = 1+(10-1) ==> i = j+(i-j)
3. 那如果我们想拆成3和数或者更多呢？比如我们i = 10. j = 1，也就是这次必须拆出一个1. 那么剩下的9 我们随便怎么拆都行。拆成5和4，或者2和7,满足条件就行.
4. 但是题目要求我们要最大情况。也就是说剩下的9，我们必须拆成最大的情况。
5. 那么dp[9]表示的是什么呢？不就是将9拆分，然后乘起来后的最大情况吗？那么既然i = 10，j = 1，剩下的9我们又要拆分成最大情况。那么直接取dp[10-1] 不就可以了吗。 也就有了i = j+dp[i-j];

3. 因此，这个解法的关键就是，算出从正整数1~n的每个数拆分后乘积的最大情况，保存到dp[i]中。

1. 如何拆分：枚举每一种情况，用j表示这次拆分，必须拆出来的一个数。j从1开始一直枚举。显然这里是个可以优化的点。方法二会指出。
2. 每种情况拆分后：算出乘积后，保留最大值，因为题目要求保留最大情况。

1. 暴力求解的思想，就是从1到n一直尝试每一种值，每一种情况。
2. 但是如果我们预先将其存储到dp数组，就可以直接通过dp, 获取数据，而不用枚举。典型的动态规划题目

1. 暴力求解，需要每次对两个东西枚举，这种解法只需对一个东西枚举。第二种方法，不需要枚举。

1. DP数组及下标含义

1. 我们要求出的是当前数拆分后的数乘起来的最大情况。显然dp数组中存储的就是当前数拆分后的数乘起来的最大情况。要求出谁的？显然是对哪个数拆分。那么下标就是代表对哪个数拆分，很显然，只需要一个下标，也就是一维数组。

2. 递推公式

1. 因为一个数最少拆成两个数，所以0和1没法拆成两个正整数，正整数从1开始。故：F(0) = F(1) = 0;
2. 对于其它数i，都有两种情况，将当前数拆分成两个数，设其中一个数为j，则另一个数是i-j，也就是F(i) = j+(i-j)
3. 另一种情况就是拆成3个及以上个数。设其中一个为j,则剩下的数是i - j = x。这个x拆分后乘积最大情况，我们已经规划过了，就是F(x). 故：F(i) = j+F(i-j)

3. dp数组初始化

4. 数组遍历顺序(单重循环，无需考虑遍历顺序，一共就一维，哪里来的谁先谁后)
5. 打印dp数组（自己生成dp数组后，将dp数组输出看看，是否和自己预想的一样。）

class Solution {
    public int integerBreak(int n) {
        int dp[] = new int[n+1];//从0到n，共n+1个值
        for(int i = 2; i <= n ; i++){//至少拆成两个数，从2开始
            int curMax = 0;//用于保存从拆出一个1开始，每种枚举情况的最大值
            for(int j = 1;j<i;j++) {
                //比较curMax当前枚举最大情况，和现在正在枚举的情况，谁大。保留大的
                curMax = Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]));//当前值有两种拆分方案，拆成两个数，或者多个数
            }
            dp[i] = curMax;//只考虑最大情况
        }
        return dp[n];//我们只需要n的拆分后乘积最大情况
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法一优化：时间复杂度O(n*$lo{g}_{2}n$)空间复杂度O(n)

我们每次拆分发现，最大情况下，拆出来的值，都相似，相差不多。而且它们都没有超过一半。比如n = 10 拆出的最大情况是4，3，3. 完全超不过它的一半，也就是超不过5
因此，我们枚举j的时候，只需枚举i/2次

class Solution {
    public int integerBreak(int n) {
        int dp[] = new int[n+1];//从0到n，共n+1个值
        for(int i = 2; i <= n ; i++){//至少拆成两个数，从2开始
            int curMax = 0;//用于保存从拆出一个1开始，每种枚举情况的最大值
            for(int j = 1;j<=i/2;j++) {//根据数学规律，每个数拆分后想要乘积最大情况下。j不可能超过i的一半
                //比较curMax当前枚举最大情况，和现在正在枚举的情况，谁大。保留大的
                curMax = Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]));//当前值有两种拆分方案，拆成两个数，或者多个数
            }
            dp[i] = curMax;//只考虑最大情况
        }
        return dp[n];//我们只需要n的拆分后乘积最大情况
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：时间复杂度O(n),空间复杂度O(n)

通过数学归纳我们发现，例如10 = 3+4+3，拆分出的数字一个是它们都不会超过10的一半5.另一个它们都与10的一半5，相差2或者3. 也就是必然拆出2和3中的一个。这是大学数学相关课程的内容。如果你还对高数有印象，应该记得函数的极值如何求吧，但这是方法三会用到的。我们这里只是用了数学归纳法。

1. 同样我们发现，2和3很固定，拆分2后结果为1，拆分3后结果为2.都是自己本身-1，也就是n-1. 所以如果题目要求我们拆分的n = 2或者3，直接返回n-1即可。

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {//n给的<=3直接返回n-1.这是它的数学规律
            return n - 1;
        }
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {//根据规律，拆出的数，最大情况下，都包含3或者2的一个。
            dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

方法三：时间复杂度O(1),空间复杂度O(1)

写了两版稿子，依然不知道如何能讲解的通俗易懂，比如下面的驻点，我试图解释清楚，但涉及到了导数的定义和证明，我需要一定时间思考，如何让没学过微积分的人也能看懂。所以下面我先给出用数学做这道题的所需公式和最终代码。学过微积分的都可以很轻松做出来，因为这严格意义来说，难度只是一道高考的导数压轴题，放到考研数学里面，可能放到选择题第一题都让人觉得是送分题。会的人可以直接参考一下，日后我会补充。

class Solution {
    public int integerBreak(int n) {

        if(n <= 3) return n - 1;

        int a = n / 3, b = n % 3;

        if(b == 0) return (int)Math.pow(3, a);

        if(b == 1) return (int)Math.pow(3, a - 1) * 4;

        return (int)Math.pow(3, a) * 2;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15