{"id":27,"date":"2018-10-30T00:09:40","date_gmt":"2018-10-30T00:09:40","guid":{"rendered":"https:\/\/andybase.com\/?p=27"},"modified":"2018-11-27T14:37:57","modified_gmt":"2018-11-27T14:37:57","slug":"931-minimum-falling-path-sum","status":"publish","type":"post","link":"https:\/\/andybase.com\/?p=27","title":{"rendered":"931 Minimum Falling Path Sum"},"content":{"rendered":"\n<p>Link\u00a0<a href=\"https:\/\/leetcode.com\/problems\/minimum-falling-path-sum\/\">931.Minimum Falling Path Sum<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Thought<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>DFS<\/strong><\/h4>\n\n\n\n<p>When first seeing this question, DFS prompt into my mind directly. Take Any node from first level as start, and search down stream. Until reach node in last level. For any path, it will have a value. Find the minimum value and it will be the answer<\/p>\n\n\n\n<p>However, for any node, it has 3 paths -> go left lower, go right lower and go direct lower. So if I have N nodes per level, the time complexity is O(3^N) which cause TLE.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">DP<\/h4>\n\n\n\n<p>Then, I find for any node, I dont quite care how it comes from the top level. What I do care is the minimum value, from any node at first level, pass level by level, then end at a specific node. So I don&#8217;t need to calculate again and again.<\/p>\n\n\n\n<p>State Transfer Equation:<br>DP[i][j] = min(DP[i-1][j-1], DP[i-1][j], DP[i-1][j+1]) + Value[i][j]<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Code<\/h2>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code brush: python; notranslate\">class Solution:\n    def minFallingPathSum(self, A):\n        \"\"\"\n        :type A: List[List[int]]\n        :rtype: int\n        \"\"\"\n        M = len(A)\n        N = len(A[0])\n        for i in range(1, M):\n            for j in range(N):\n                if j == 0:\n                    A[i][j] = min(A[i-1][j], A[i-1][j+1]) + A[i][j]\n                elif j == N - 1:\n                    A[i][j] = min(A[i-1][j], A[i-1][j-1]) + A[i][j]\n                else:\n                    A[i][j] = min((A[i-1][j], A[i-1][j+1],A[i-1][j-1],)) + A[i][j]\n        return min(A[-1])<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Runtime<\/h2>\n\n\n\n<p>Time O(N^2)<br>\nSpace O(N^2)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Link\u00a0931.Minimum Falling Path Sum Thought DFS When first seeing this question, DFS prompt into my mind directly. Take Any node [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"enabled":false},"version":2}},"categories":[2],"tags":[4,3],"class_list":["post-27","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-contest","tag-leetcode"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paWPni-r","_links":{"self":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/27","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=27"}],"version-history":[{"count":5,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/27\/revisions"}],"predecessor-version":[{"id":78,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/27\/revisions\/78"}],"wp:attachment":[{"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=27"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=27"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=27"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}