343. 整数拆分 - Java 动态规划 背包DP

原题地址：https://leetcode.cn/problems/integer-break/

题解

这题某种意义上也是322. 零钱兑换 的变种

• 只是硬币固定为[1,n]中的所有数，且优先条件为乘积的最大值而非取值次数的最小值

设dp[i]为拆分i得到的最大乘积，遍历j∈(0,i)，我们可以将i从j拆成两份：i-j和j作为乘积的两个因子

• 这里j不包括边界是因为dp[i]已经默认了i是必然被拆分的，而j取0/i则是没有被拆分的情况

拿i-j来说，我们可以选择不继续拆分i-j或是拆分i-j中较大的选择作为乘积的左因子，而右因子j也是同理，于是就有：

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int integerBreak(int n) {
        int[] dp=new int[n+1];
        boolean[] available=new boolean[n+1];
        dp[1]=1;
        available[1]=true;

        int mul;
        boolean flag;
        for(int i=2;i<=n;i++){
            mul=0;
            flag=false;
            for(int j=1;j<n;j++){
                if(i-j>=0&&available[i-j]){
                    mul=Math.max(mul,Math.max(dp[i-j],i-j)*Math.max(dp[j],j));
                    flag=true;
                }
            }
            if(flag){
                dp[i]=mul;
                available[i]=true;
            }
        }

        if(available[n])
            return dp[n];
        else
            return -1;
    }
}