AC Java DP solutions


  • 0
    S

    bottom up

    public class Solution {
        public int integerBreak(int n) {
            int[] max = new int[n+1];
            max[1]=1;
            for(int i=1;i<=n;i++) {
                int m=0;
                for(int j=1;j<=i/2;j++){
                    int left=max[j];
                    int right = max[i-j];
                    m=Integer.max(m,left*right);
                    m=Integer.max(m,j*right);
                    m=Integer.max(m,left*(i-j));
                    m=Integer.max(m,j*(i-j));
                }
                max[i]=m;
            }
            return max[n];
        }
    }
    

    top down

    public class Solution {
        
        public int integerBreak(int n) {
            int[] mem = new int[n+1];
            integerBreakR(n,mem);
            return mem[n];
        }
        
          public int integerBreakR(int n, int[] mem) {
            if(mem[n]!=0) return mem[n];
            if (n==1) return 1;
            int max=0;
            for(int i=1;i<=n/2;i++){
                int left = integerBreakR(i,mem);
                int right = integerBreakR(n-i,mem);
                max = Integer.max(max,left*right);
                max = Integer.max(max,i*right);
                max = Integer.max(max,left*(n-i));
                max = Integer.max(max,i*(n-i));
            }
            mem[n]=max;
            return max;
        }
    }
    

Log in to reply
 

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