add 650

fishercoder1534 · fishercoder1534 · commit c53bfa6f6045 · 2017-07-30T08:55:11.000-07:00
diff --git a/README.md b/README.md
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|650|[2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_650.java) | O(n^2) |O(n) | Medium | DP
 |648|[Replace Words](https://leetcode.com/problems/replace-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_648.java) | O(n) |O(n) | Medium | Trie
 |647|[Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_647.java) | O(n^2) |O(1) | Medium | DP
 |646|[Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_646.java) | O(nlogn) |O(1) | Medium | DP
diff --git a/src/main/java/com/fishercoder/solutions/_650.java b/src/main/java/com/fishercoder/solutions/_650.java
@@ -0,0 +1,40 @@
+package com.fishercoder.solutions;
+
+/**
+ * 650. 2 Keys Keyboard
+ *
+ * Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
+
+ Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
+ Paste: You can paste the characters which are copied last time.
+ Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
+
+ Example 1:
+ Input: 3
+ Output: 3
+
+ Explanation:
+ Intitally, we have one character 'A'.
+ In step 1, we use Copy All operation.
+ In step 2, we use Paste operation to get 'AA'.
+ In step 3, we use Paste operation to get 'AAA'.
+
+ Note:
+ The n will be in the range [1, 1000].
+ */
+public class _650 {
+
+    public int minSteps(int n) {
+        int[] dp = new int[n+1];
+        for (int i = 2; i <= n; i++) {
+            dp[i] = i;//we assign i to dp[i] first, because for a lot of cases, e.g. for most cases when i is odd, its min steps is i itself, if it's not, we can overwrite it later
+            for (int j = i-1; j > 1; j--) {//traverse backwards, whenever it's divisible by j, we'll update dp[i] because it's guaranteed to be smaller when j is smaller.
+                if (i % j == 0) {
+                    dp[i] = dp[j] + (i/j);
+                    break;
+                }
+            }
+        }
+        return dp[n];
+    }
+}
diff --git a/src/test/java/com/fishercoder/_650Test.java b/src/test/java/com/fishercoder/_650Test.java
@@ -0,0 +1,44 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._650;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 7/30/17.
+ */
+public class _650Test {
+    private static _650 test;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _650();
+    }
+
+    @Test
+    public void test1(){
+        assertEquals(3, test.minSteps(3));
+    }
+
+    @Test
+    public void test2(){
+        assertEquals(9, test.minSteps(20));
+    }
+
+    @Test
+    public void test3(){
+        assertEquals(19, test.minSteps(19));
+    }
+
+    @Test
+    public void test4(){
+        assertEquals(0, test.minSteps(1));
+    }
+
+    @Test
+    public void test5(){
+        assertEquals(35, test.minSteps(741));
+    }
+}
