Java simple Solution


  • 0
    Z
    //go on populating dp array starting from index 2, if any of the index is product of previous two indices, then jus add the number of steps
    //n=1 -> 1 step
    //n=2 -> 2 steps
    //n=3 -> 3 steps
    //n=4 -> 2steps*2steps = 4steps
    //n=5 -> 5 steps
    //n=6 -> 3steps * 2steps = 6steps
    public int minSteps(int n) {
           if(n<=1)return 0;
            int[] dp = new int[n+1];
            for(int i=2; i<n+1; i++){ 
                int j=i;
                for(int k=2; k<j/2; k++){
                    if(j%k==0){
                        int m=j/k;
                        dp[i]=dp[m]+dp[k];
                        break;
                    }
                }
                if(dp[j]==0){
                    dp[j] = j;
                }
            }
            return dp[n];
        }
    

Log in to reply
 

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