2-keys-keyboard

gistfile1.txt

class Solution {
    /*
    public int minSteps(int n) {
        int[] dp = new int[n+1];
        for(int i=0; i <= n; i++) {
            dp[i] = -1;
        }
        return recurse(dp, n);
    }
    public int recurse(int[] dp, int currNum) {
        if(currNum == 1) { 
            return 0;
        }
        if (dp[currNum] != -1) {
            return dp[currNum];
        }
        for(int i = currNum/2; i >1; i--) {
            if( currNum % i == 0) {
                dp[currNum] = recurse(dp, i) + currNum/i; // dp[3] + 3->9 =  dp[3] + 9/3(including copy)
                return dp[currNum];
            }
        }
        dp[currNum] = currNum;
        return currNum;          
    }
    */
    //pure recursive
    /*
   public int minSteps(int n) {
        if (n == 1) return 0;
        for (int i = n / 2; i > 1; i--) {
            if (n % i == 0) {
                return minSteps(i) + n / i;//
            }
        }
        return n;
    }
    */
    //pure iterative
    public int minSteps(int n) {
        int[] dp = new int[n+1];
        for(int i=2; i <= n; i++) {
            dp[i] = i;
            for(int j = i/2; j > 1 ; j--) {
                if (i % j == 0) {
                    dp[i] = dp[j] + i/j;
                    break;
                }
            }
        }
        return dp[n];
    }
}