leetCode-343:Integer Break

问题描述

给定一个2~58的整数，这个整数表示成多个数的和，要求求出拆分的这些子数的积的最大值。题目链接如下：**点我**

样例输入输出

输入：2

输出：1

解释：2 = 1 + 1，积为 1 * 1 = 1

输入：10

输出：36

解释：10 = 3 + 3 + 4，积为：3 * 3 * 4 = 36，其他组合的值都比36 小

问题解法

用动态规划，用 dp[i] 表示整数 i 拆分的子树乘积最大值，则动态转移方程为：dp[i] = max(dp[i], max(dp[j], j) * max(dp[i - j], i - j))，其中 j <= i / 2代码如下

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