DP solution


  • 0
    B

    You can think of it as a tree and for each node you want to get the max value of its children , for example if n = 4 , 4 can be reached by 4-1 => check (3) solution * 1 or 4-2 => check(2) solution * 2 , for 3 -> 3 can be reached by 3-1 => 2 -> and 2 can be reached by 2 - 1 => 1 and we can say state of [1] will be 0 as base case, So state[2] will equal the maximum between dividing 2 to (1+1) or return 2 it self so state[2] = 2 , returning to state of 3 which will be the maximum between state[2] * 1 which is 2*1 or returning 3 it self so state[3] = 3 returning back to state[4] = state[3] * 1 and then try (2) solution * 2 we will find that we already solved state[2] so state[4] = max(state[3]*1,state[2]*2) returning 4

    public class Solution {
        public int solve(int n,int m,int state[]){
            if(state[n] != -1)
                return state[n];
            int mx = -1;
            for(int i = 1;i <= n/2;i++){
                mx = Math.max(mx,solve(n-i,m,state)*i);
            }
            state[n] = mx;
            if(n !=  m)
                state[n] = Math.max(mx,n);
            return state[n]; 
        }
        public int integerBreak(int n) {
            int state[] = new int [n+1];
            for(int i = 2;i < n+1;i++)
                state[i] = -1;
            state[0] = 0;
            state[1] = 1;
            if(n == 1)
                return 0;
            return solve(n,n,state);
        }
    }
    

Log in to reply
 

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