1289 solved.

liuyubobobo · liuyubobobo · commit c27f16e5bbfc · 2023-08-09T22:15:13.000-07:00
diff --git a/1001-1500/1289-Minimum-Falling-Path-Sum-II/cpp-1289/CMakeLists.txt b/1001-1500/1289-Minimum-Falling-Path-Sum-II/cpp-1289/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.25)
+project(cpp_1289)
+
+set(CMAKE_CXX_STANDARD 17)
+
+add_executable(cpp_1289 main.cpp)
diff --git a/1001-1500/1289-Minimum-Falling-Path-Sum-II/cpp-1289/main.cpp b/1001-1500/1289-Minimum-Falling-Path-Sum-II/cpp-1289/main.cpp
@@ -0,0 +1,43 @@
+/// Source : https://leetcode.com/problems/minimum-falling-path-sum-ii/
+/// Author : liuyubobobo
+/// Time   : 2023-08-09
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Memoization
+/// Time Complexity: O(n^3)
+/// Space Complexity: O(n^2)
+class Solution {
+public:
+    int minFallingPathSum(vector<vector<int>>& grid) {
+
+        int n = grid.size();
+
+        vector<vector<int>> dp(n, vector<int>(n + 1, -1));
+        return dfs(n, grid, 0, n, dp);
+    }
+
+private:
+    int dfs(int n, const vector<vector<int>>& grid, int row, int last_c, vector<vector<int>>& dp) {
+
+        if (row == n) return 0;
+        if (dp[row][last_c] != -1) return dp[row][last_c];
+
+        int res = INT_MAX;
+        for (int j = 0; j < n; j ++) {
+            if (j == last_c) continue;
+            res = min(res, grid[row][j] + dfs(n, grid, row + 1, j, dp));
+        }
+        return dp[row][last_c] = res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -1256,7 +1256,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 1286 | [Iterator for Combination](https://leetcode.com/problems/iterator-for-combination/) | [solution](https://leetcode.com/problems/iterator-for-combination/solution/) | [C++](1001-1500/1286-Iterator-for-Combination/cpp-1286/) | | |
 | | | | | | |
 | 1288 | [Remove Covered Intervals](https://leetcode.com/problems/remove-covered-intervals/) | [solution](https://leetcode.com/problems/remove-covered-intervals/solution/) | [C++](1001-1500/1288-Remove-Covered-Intervals/cpp-1288/) | | |
-| | | | | | |
+| 1289 | [Minimum Falling Path Sum II](https://leetcode.com/problems/minimum-falling-path-sum-ii/) | [无] | [C++](1001-1500/1289-Minimum-Falling-Path-Sum-II/cpp-1289/) | | |
 | 1290 | [Convert Binary Number in a Linked List to Integer](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/) | [solution](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/solution/) | [C++](1001-1500/1290-Convert-Binary-Number-in-a-Linked-List-to-Integer/cpp-1290/) | | |
 | 1291 | [Sequential Digits](https://leetcode.com/problems/sequential-digits/) | [solution](https://leetcode.com/problems/sequential-digits/solution/) | [C++](1001-1500/1291-Sequential-Digits/cpp-1291/) | | |
 | | | | | | |
