My 1ms DP Solution, Intuitive, without Math consideration of 2 or 3


  • 1

    The idea is to maximize:

    • f(n) = f(i)*f(n-i)
    • It is intuitive to use DP then

    It is easier for me to come up with this DP solution. The highest-voted solution is considering math, about factoring 2 or 3, while it is not easy for me to make such a thought.

    Attached is my 1ms AC code:

    public class Solution {
      int[] dict;
      public int integerBreak(int n) {
        dict = new int[n+1];
        //Handle n=2 and n=3
        if(n<=3) return n-1;
        return helper(n);
      }
      private int helper(int n){
        if(n<=4) return n;
        if(dict[n]!=0) return dict[n];
        int res = 0;
        for(int i=2;i<=n/2;i++){
          int tmp1=helper(i), tmp2 = helper(n-i);
          int tmp = tmp1*tmp2;
          if(res<tmp)
            res = tmp;
        }
        dict[n]=res;
        return dict[n];
      }
    }

Log in to reply
 

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