package leetcode;

/**
 * https://leetcode.com/problems/2-keys-keyboard/
 */
public class Problem650 {
    public int minSteps(int n) {
        return minSteps(1, n, 1);
    }

    private static int minSteps(int n, int m, int x) {
        if (n == m) {
            return 1;
        } else if (n > m) {
            return 0;
        }
        int a = minSteps(n - x, m, x) + 1;
        int b = minSteps(n, m, n);
        int min = Math.min(a, b);
        return min;
    }

    public static void main(String[] args) {
        Problem650 prob = new Problem650();
        System.out.println(prob.minSteps(3)); // 3
    }
}

@@ -125,24 +125,70 @@
 ps(int n) %7B%0A
+        Integer%5B%5D%5B%5D memo = new Integer%5Bn%5D%5Bn%5D;%0A
         retu
@@ -206,16 +206,22 @@
 (1, n, 1
+, memo
 );%0A    %7D
@@ -262,23 +262,41 @@
 int 
-n
+m
 , int 
-m
+n
 , int x
+, Integer%5B%5D%5B%5D memo
 ) %7B%0A
@@ -316,59 +316,198 @@
  == 
-m) %7B%0A            return 1;%0A        %7D else if (n %3E m
+1) %7B%0A            return 0;%0A        %7D%0A        if (m == n) %7B%0A            return 1;%0A        %7D%0A        if (m %3E n) %7B%0A            return Integer.MAX_VALUE;%0A        %7D%0A        if (memo%5Bm%5D%5Bx%5D != null
 ) %7B%0A
@@ -517,33 +517,42 @@
          return 
-0
+memo%5Bm%5D%5Bx%5D
 ;%0A        %7D%0A    
@@ -576,25 +576,91 @@
 eps(
-n -
+m +
  x, 
-m, x) + 1;
+n, x, memo);%0A        if (a %3C Integer.MAX_VALUE) %7B%0A            a++;%0A        %7D
 %0A   
@@ -685,15 +685,25 @@
 eps(
+m + m, 
 n, m, 
-n
+memo
 );%0A 
@@ -714,199 +714,177 @@
    i
-nt min = Math.min(a, b);%0A        return min;%0A
+f (b %3C Integer.MAX_VALUE) %7B%0A            // copy all + paste%0A            b += 2;%0A   
     
+ 
 %7D
-%0A
 %0A    
-public static void
+    int
  m
-a
 in
-(String%5B%5D args) %7B%0A        Problem650 prob = new Problem650();%0A        System.out.println(prob.minSteps(3)); // 3
+ = Math.min(a, b);%0A        memo%5Bm%5D%5Bx%5D = min;%0A        return min;
 %0A   

Solve problem 650