Leetcode 931 - Minimum Falling Path Sum

題目

Problem#

給你一個 nxn 的陣列，問你從上面走到最下面最短路徑總和為多少?
可以左右斜著走，但只能往下走，意即對於位置 $(i, j)$ 可以往 $(i+1, j-1)$ (左下), $(i+1, j)$ (下方), $(i+1, j-1)$ (右下) 走

想法#

對於起點 $(i, j)$ 可以往三個方向走，令 $f(i, j) = 最短路徑總和$ 則可以給出 $f(i, j) = min(f(i+1, j-1), f(i+1, j), f(i+1, j+1))$，接著加上 dp 表格用於記憶化搜索

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n^2)$

AC Code#

top-down dp

賞析#

https://leetcode.com/problems/minimum-falling-path-sum/solutions/2108185/minimum-falling-path-sum/?orderBy=hot

心得#

原本直覺暴力枚舉第一排 DFS ($\mathcal{O}(n^3)$) 會過，但後來看題解要 dp QQ
看來 leetcode 測資都給很多