0931 added.

liuyubobobo · liuyubobobo · commit dfc2f44b032b · 2018-10-29T03:19:44.000-07:00
diff --git a/0931-Minimum-Path-Falling-Sum/cpp-0931/CMakeLists.txt b/0931-Minimum-Path-Falling-Sum/cpp-0931/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(C)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(C ${SOURCE_FILES})
diff --git a/0931-Minimum-Path-Falling-Sum/cpp-0931/main.cpp b/0931-Minimum-Path-Falling-Sum/cpp-0931/main.cpp
@@ -0,0 +1,42 @@
+/// Source : https://leetcode.com/problems/minimum-falling-path-sum/
+/// Author : liuyubobobo
+/// Time   : 2018-10-27
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Dynamic Programming
+/// Time Complexity: O(m * n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int minFallingPathSum(vector<vector<int>>& A) {
+
+        int m = A.size();
+        if(m == 0) return 0;
+
+        int n = A[0].size();
+        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
+
+        dp[0] = A[0];
+        for(int i = 1; i < m; i ++)
+            for(int j = 0; j < n; j ++)
+                for(int k = max(j - 1, 0); k <= min(n - 1, j + 1); k ++)
+                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + A[i][j]);
+
+        return *min_element(dp[m - 1].begin(), dp[m - 1].end());
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> A = {{1,2,3},{4,5,6},{7,8,9}};
+    cout << Solution().minFallingPathSum(A) << endl;
+    // 12
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -576,4 +576,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 928 | [Minimize Malware Spread II](https://leetcode.com/problems/minimize-malware-spread-ii/description/) | [solution](https://leetcode.com/problems/minimize-malware-spread-ii/solution/) | [C++](0928-Minimize-Malware-Spread-II/cpp-0928/) | | |
 | 929 | [Unique Email Addresses](https://leetcode.com/problems/unique-email-addresses/) | [solution](https://leetcode.com/problems/unique-email-addresses/) | [C++](0929-Unique-Email-Addresses/cpp-0929/) | | |
 | 930 | [Binary Subarrays With Sum](https://leetcode.com/problems/binary-subarrays-with-sum/) | [solution](https://leetcode.com/problems/binary-subarrays-with-sum/) | [C++](0930-Binary-Subarrays-With-Sum/cpp-0930/) | | |
+| 931 | [Minimum Path Falling Sum](https://leetcode.com/problems/minimum-falling-path-sum/) | [solution](https://leetcode.com/problems/minimum-falling-path-sum/) | [C++](0931-Minimum-Path-Falling-Sum/cpp-0931/) | | |
 | | | | | | |
