add 746

fishercoder1534 · fishercoder1534 · commit 84d0e29bd341 · 2017-12-17T10:26:07.000-08:00
diff --git a/README.md b/README.md
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
 |748|[Shortest Completing Word](https://leetcode.com/problems/shortest-completing-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_748.java) | O(n) | O(1) | Easy|
+|746|[Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_746.java) | O(n) | O(1) | Easy|
 |744|[Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_744.java) | O(logn) | O(1) | Easy|
 |739|[Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_739.java) | O(n^2) | O(1) | Medium| 
 |738|[Monotone Increasing Digits](https://leetcode.com/problems/monotone-increasing-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_738.java) | O(n) | O(1) | Medium|
diff --git a/src/main/java/com/fishercoder/solutions/_746.java b/src/main/java/com/fishercoder/solutions/_746.java
@@ -0,0 +1,37 @@
+package com.fishercoder.solutions;
+
+/**
+ * 746. Min Cost Climbing Stairs
+ *
+ * On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
+ * Once you pay the cost, you can either climb one or two steps.
+ * You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
+
+ Example 1:
+ Input: cost = [10, 15, 20]
+ Output: 15
+ Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
+
+ Example 2:
+ Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
+ Output: 6
+ Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
+
+ Note:
+ cost will have a length in the range [2, 1000].
+ Every cost[i] will be an integer in the range [0, 999].
+ */
+
+public class _746 {
+  public static class Solution1 {
+    public int minCostClimbingStairs(int[] cost) {
+      int[] dp = new int[cost.length];
+      dp[0] = cost[0];
+      dp[1] = Math.min(cost[1], cost[0] + cost[1]);
+      for (int i = 2; i < cost.length; i++) {
+        dp[i] = Math.min(dp[i-1] + cost[i], dp[i-2] + cost[i]);
+      }
+      return Math.min(dp[cost.length-1], dp[cost.length-2]);
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_746Test.java b/src/test/java/com/fishercoder/_746Test.java
@@ -0,0 +1,29 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._746;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _746Test {
+  private static _746.Solution1 solution1;
+  private static int[] cost;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _746.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    cost = new int[] {10, 15, 20};
+    assertEquals(15, solution1.minCostClimbingStairs(cost));
+  }
+
+  @Test
+  public void test2() {
+    cost = new int[] {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
+    assertEquals(6, solution1.minCostClimbingStairs(cost));
+  }
+}
