add 931

fishercoder1534 · fishercoder1534 · commit df8bfaebd654 · 2020-02-26T17:11:10.000-08:00
diff --git a/README.md b/README.md
@@ -174,6 +174,7 @@ _If you like this project, please leave me a star._ &#9733;
 |937|[Reorder Log Files](https://leetcode.com/problems/reorder-log-files/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_937.java) | |Easy|
 |935|[Knight Dialer](https://leetcode.com/problems/knight-dialer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_935.java) | |Medium|
 |933|[Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_933.java) | |Easy|
+|931|[Minimum Falling Path Sum](https://leetcode.com/problems/minimum-falling-path-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_931.java) | |Medium|Dynamic Programming
 |929|[Unique Email Addresses](https://leetcode.com/problems/unique-email-addresses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_929.java) | |Easy|
 |925|[Long Pressed Name](https://leetcode.com/problems/long-pressed-name/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_925.java) | |Easy|
 |922|[Sort Array By Parity II](https://leetcode.com/problems/sort-array-by-parity-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_922.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_931.java b/src/main/java/com/fishercoder/solutions/_931.java
@@ -0,0 +1,52 @@
+package com.fishercoder.solutions;
+
+/**
+ * 931. Minimum Falling Path Sum
+ *
+ * Given a square array of integers A, we want the minimum sum of a falling path through A.
+ * A falling path starts at any element in the first row, and chooses one element from each row.
+ * The next row's choice must be in a column that is different from the previous row's column by at most one.
+ *
+ * Example 1:
+ * Input: [[1,2,3],[4,5,6],[7,8,9]]
+ * Output: 12
+ * Explanation:
+ * The possible falling paths are:
+ * [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
+ * [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
+ * [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
+ * The falling path with the smallest sum is [1,4,7], so the answer is 12.
+ *
+ * Note:
+ * 1 <= A.length == A[0].length <= 100
+ * -100 <= A[i][j] <= 100
+ * */
+public class _931 {
+    public static class Solution1 {
+        public int minFallingPathSum(int[][] A) {
+            int size = A.length;
+            int[][] dp = new int[size][size];
+            for (int i = 0; i < size; i++) {
+                for (int j = 0; j < size; j++) {
+                    if (i == 0) {
+                        dp[i][j] = A[i][j];
+                    } else {
+                        int lastRow = dp[i - 1][j];
+                        if (j - 1 >= 0) {
+                            lastRow = Math.min(dp[i - 1][j - 1], lastRow);
+                        }
+                        if (j + 1 < size) {
+                            lastRow = Math.min(dp[i - 1][j + 1], lastRow);
+                        }
+                        dp[i][j] = lastRow + A[i][j];
+                    }
+                }
+            }
+            int minSum = Integer.MAX_VALUE;
+            for (int i = 0; i < size; i++) {
+                minSum = Math.min(minSum, dp[size - 1][i]);
+            }
+            return minSum;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_931Test.java b/src/test/java/com/fishercoder/_931Test.java
@@ -0,0 +1,28 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._931;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _931Test {
+    private static _931.Solution1 solution1;
+    private static int[][] A;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _931.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        A = new int[][]{
+                {1, 2, 3},
+                {4, 5, 6},
+                {7, 8, 9}
+        };
+        assertEquals(12, solution1.minFallingPathSum(A));
+    }
+
+}
