Simple Java DP solution with comments


  • 2
    J
    public class Solution {
    public int integerBreak(int n) {
    	// dp[i] denotes the maximum product breaking i, then we have state equation:
    	// dp[i] = max (dp[i], max(i-j, dp[i-j]) * max(j, dp[j])) for 1 <= j < i,
        // that is, the max of all possible ways of breaking i into (i-1, 1), (i-2, 2)... (1, i -1).
    
        int[] dp = new int[n + 1];
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) {
        	for (int j = 1; j < i; j++) {
        		dp[i] = Math.max(dp[i],  Math.max(i - j, dp[i-j]) * Math.max(j, dp[j]));
        	}
        }
        return dp[n];
    } }

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

  • 0
    P

    we can change j < i to j <= i / 2


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.