七夕力扣刷不停，343. 整数拆分（剑指 Offer 14- I. 剪绳子、剑指 Offer 14- II. 剪绳子 II）

https://leetcode-cn.com/problems/integer-break/
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

根据以上思路得动态规划状态转移方程dp表达式
dp[n] = max(dp[n],dp[j]*dp[n-j]);
这里解释一下，就是可以选择直接是dp[n]，或者将dp[n]划分为两个数，看这两个数的乘积和不划分的dp[n],这两个哪个比较大。
有时候划分了可能会变小，比如dp[2],dp[3]
dp6中可能包括多个dp[2]或者3，所以，这个时候就要考虑，是否要继续划分的问题。
dp[n]:长度为n的数获得的乘积的最大值

class Solution {
    public int integerBreak(int n) {
        //动态规划
        //base case
        int[] dp = new int[n+1];
        if(n<2){
            return 1;
        }
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        //这里要说明一下，因为对于2、3，再拆分就会越来越小，
        //所以就不拆分了，只要答案对就行，也不能太纠结
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
		//双层for循环，动态规划经典标志
        for(int i=4;i<=n;i++){
            for(int j=1;j<=(i/2);j++){
                dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int integerBreak(int n) {
    if(n<=2){
            return 1; 
        }
        if(n==3){
            return 2;
        }

        int[] dp = new int[n+1];
        //基础的就不分了，因为会越分越小
        dp[1]=1;dp[2]=2;dp[3]=3;
        // dp[1]=1;
        // dp[2]=2;
        // dp[3]=3;
        for(int i=4;i<=n;i++){
            for(int j=1;j<=(i/2);j++){
                dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
            }
        }
        return dp[n];
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

代码一样，只是出现了一个bug，调试一下，就好了

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        if(n<=2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        //双层for循环，经典动态规划标志
        for(int i=4;i<=n;i++){
        //这里的j忘记写=了
            for(int j=1;j<=(i/2);j++){
                System.out.println(dp[i]);
                System.out.println(dp[j]*dp[i-j]);
                dp[i] =  Math.max(dp[i],dp[j]*dp[i-j]);
                System.out.println(dp[i]);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

参考链接：
LeetCode每日打卡.343.整数拆分

剑指 Offer 14- II. 剪绳子 II
https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/wu-xu-fu-za-shu-xue-jiang-jie-dong-tai-g-j470/

class Solution {
public:
    int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        vector<int> products(n + 1, 0);
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;
        int maxVal = 0;
        for (int i = 4; i <= n; ++i) {
            maxVal = 0;
            for (int j = 1; j <= i / 2; ++j) {
                maxVal = max(maxVal, products[j] * products[i - j]);
            }
            products[i] = maxVal;
        }
        return products[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int cuttingRope(int n) {
        /**
            思路：动态规划
            费曼学习法一遍
            动态规划是一种穷举，然后可以避免我们重复计算
            我们先自上而下考虑：
                比如，对于一个绳子n，我们可以先切一刀
                然后，获取两段，那么我们可以有n-1种切法，因为n要求是整数
                然后可以对其中一段，再进行切
                获取若干段，不断重复这个过程
                最后直到分为不可以再分的段数，然后我们
            再自下而上的考虑：
                然后根据求出的每段的最大值，来考虑该段是否需要进行划分
                由于有一些边界条件限制，所以我们应该先初始化
         */
        
        if(n<2){
            return 1;
        }   
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2; 
        }
       
        int[] dp = new int[n+1];
        //由公式可以证明，当n小于4的时候，不分开获取的结果会更大一些
        //我们的dp数组，就是按照不分开进行计算的
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        //穷举每一种可能
        for(int i=4;i<=n;i++){
            //每一种可能是否需要划分
            for(int j=1;j<=(i/2);j++){
                //是否划分，划分后大还是不划分大，整一个for循环，来寻找dp[i]的最大值
                dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
            }
        } 
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44