[数据结构与算法]LeetCode | 343. Integer Break

题目

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

2 <= n <= 58

代码

class Solution {
public:
    int integerBreak(int n) {
        if(n == 1 || n == 2)
            return 1;
        if(n == 3)
            return 2;
        int *dp = new int [n+1];
        memset(dp, 0, sizeof(int)*(n+1));
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4; i<=n; i++){
            int idx1, idx2;
            for(idx1=1; idx1<=i/2; idx1 ++){
                idx2 = i - idx1;
                dp[i] = max(dp[i], dp[idx1]*dp[idx2]);
            }
        }
        return dp[n];
    }
};

转眼，七月就这么过去了~七月是夏天的，七月是忙碌的，希望在向前走的路上，不忘初心。最近工作上的项目多重叠加，生活中也有些收尾的事情，整体来说时间很匆忙，一直在往前赶。

无论如何，都不能忘记为什么出发。最后，以今天看到的一句美丽的话作为结尾：
“我给你，早在你出生前多年的一个傍晚看到的一朵黄玫瑰花的记忆。”

生活中的诗意是多么难得和宝贵的时刻呀，愿大家都有一个灿烂淋漓，又惬意的夏日。我们八月再见。