Cinte's Leetcode Record
0%

343. Integer Break

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

343. Integer Break

dp
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; ++i)
            for(int j = 1; j < i; ++j)
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
        return dp.back();
    }
};

对于一个数，截成两段，挨个尝试，每一段由于那个数字在运算时候是不计算他本身的，所以后面用时候需要比较他自己和他break后谁打，所以要有这么多max

数学方法优化

discussion 

1
2
3
4
5
6
7
8
You're making it pretty complicated.

If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

For the rest I agree, 3*3 is simply better than 2*2*2, so you'd never use 2 more than twice.

6 = 2 + 2 + 2 = 3 + 3. But 2 * 2 * 2 < 3 * 3.
Therefore, if there are three 2's in the decomposition, we can replace them by two 3's to gain a larger product.
存在大于4的因子时候，他永远可以被拆到小于4，因此只需要1，2，3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; ++i)
            dp[i] = max(3 * max(i - 3, dp[i - 3]) ,max(dp[i - 1], 2 * max(i - 2, dp[i - 2]))); // 此处dp[i - 1]而不是max(dp[i - 1], i - 1)是因为i>3时，2 * (i - 2) > 1 * (i - 1)
        return dp.back();
    }
};

空间优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        int a = 0;
        int b = 1;
        int c = 1;
        for(int i = 3; i <= n; ++i)
        {
            a = max(max(dp[i - 1], max(i - 2, dp[i - 2]) * 2), max(a, i - 3) * 3);
            swap(a, b);
            swap(b, c);
        }
        return c;
    }
};
##### 纯数学 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
        if(n <= 3)
            return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 1)
            return pow(3, a - 1) * 4;
        if(b == 2)
            return pow(3, a) * 2;
        return pow(3, a);
    }
};