LeetCode 343 整数拆分

LeetCode 343 整数拆分

给定一个正整数，将其拆分为至少2个正整数之和，求出拆分后所有数的最大乘积

1. 递归(暴力)，对于数n，每次将其拆分为两个数:curr(本次拆分值)、rem(剩余值)，并递归调用对rem继续拆分直到为0、1
2. 记忆化递归，将对每次rem的最优拆分结果进行保存，避免重复计算

class Solution_LC_343 {
    public int integerBreak(int n) {
        //记忆数组
        int[] memo = new int[n];
        int ans = 0;
        //i表示第一个拆分值，该值必须小于n，因此不放在递归中
        for(int i=1; i<n; i++) {
            int tmp = integerBreak(n-i, i, memo);
            ans = (ans>tmp)? ans:tmp;
        }

        return ans;
    }
    //记忆化递归，memo[]存储每个数rem的最优解 (0< rem < n)
    public int integerBreak(int rem, int curr, int memo[]) {
        //剩余拆分值为0，1不需要继续向下拆分
        if(rem==0 || rem==1) {
            return curr;
        }

        int result = 0;
        if(memo[rem]==0) {
            for(int i=1; i<=rem; i++) {
                int tmp = integerBreak(rem-i, i, memo);
                result = (result>tmp)? result:tmp;
            }
        }
        else {
            result = memo[rem];
        }

        return curr*result;
    }
}

2. 动态规划(优化)

class Solution_LC_343 {
    public int integerBreak(int n) {
        //dp[i]表示对i进行拆分后得到的最优解
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                //比较对剩余拆分之(i-j)不进行拆分、进行拆分两种结果
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}