Math Solution is Good, but DP Solution is also good to know


  • 0

    If we use DP to solve this problem, time complexity is O(n^2), but it turns out that it is not too slow. So it's still good to know.

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

Log in to reply
 

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