Why 2 or 3? We are practicing programming after all. Java DP solution without math.


  • 0

    I am really appreciate those who use pure mathematics to solve this problem such as this post, but I am recently studying DP and filter the problems by tag Dynamic Programming, I am therefore posting my Java straight forward solution here in case anyone who is in the same situation as me.

    public class Solution {
        public int integerBreak(int n) {
    		/*
    		 * dp: the index of the first dimension denotes the number to be broken (10 in the given example)
    		 *	   the index of the second dimension denotes the number of first part
    		 */
    		int[][] dp = new int[n + 1][n + 1];
    		for (int i = 1; i <= n; i++) 
    			dp[i] = new int[n + 1];
    		for (int i = 1; i <= n; i++) {
    			dp[i][1] = i;
    			dp[i][i] = 1;	// all divisions are all 1s, the product is therefore 1
    		}
    		for (int i = 2; i <= n; i++)
    			for (int j = 2; j <= i; j++)
    				for (int k = 1; k < i; k++)
    					dp[i][j] = Math.max(dp[i][j], k * dp[i - k][j - 1]);
    
    		int result = 0;
    		for (int i = 2; i <= n; i++)
    			result = Math.max(result, dp[n][i]);
    		return result;
        }
    }
    

Log in to reply
 

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