{"id":826,"date":"2025-08-02T18:04:15","date_gmt":"2025-08-02T12:34:15","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=826"},"modified":"2025-08-02T18:04:16","modified_gmt":"2025-08-02T12:34:16","slug":"minimum-path-sum","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/","title":{"rendered":"Minimum Path Sum | Leetcode 64 | All 4 DP Solutions"},"content":{"rendered":"\n<p>Given a&nbsp;<code>m x n<\/code>&nbsp;<code>grid<\/code>&nbsp;filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/minimum-path-sum\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;You can only move either down or right at any point in time.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/11\/05\/minpath.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> grid = [[1,3,1],[1,5,1],[4,2,1]]<br><strong>Output:<\/strong> 7<br><strong>Explanation:<\/strong> Because the path 1 \u2192 3 \u2192 1 \u2192 1 \u2192 1 minimizes the sum.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> grid = [[1,2,3],[4,5,6]]<br><strong>Output:<\/strong> 12<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>m == grid.length<\/code><\/li>\n\n\n\n<li><code>n == grid[i].length<\/code><\/li>\n\n\n\n<li><code>1 &lt;= m, n &lt;= 200<\/code><\/li>\n\n\n\n<li><code>0 &lt;= grid[i][j] &lt;= 200<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-b8b739e0-8cb2-47b2-a452-a7f19ed5ea18\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#0-approach-1-recursion-brute-force\" style=\"\">Approach 1: Recursion (Brute Force)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#2-detailed-steps\" style=\"\">Detailed Steps<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#3-code-with-comments\" style=\"\">Code (with comments)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#6-approach-2-memoization-top-down-dp\" style=\"\">Approach 2: Memoization (Top-Down DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#7-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#8-detailed-steps\" style=\"\">Detailed Steps<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#9-code-with-comments\" style=\"\">Code (with comments)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#10-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#11-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#12-approach-3-tabulation-bottom-up-dp\" style=\"\">Approach 3: Tabulation (Bottom-Up DP)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#13-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#14-detailed-steps\" style=\"\">Detailed Steps<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#15-code-with-comments\" style=\"\">Code (with comments)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#16-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#17-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#18-approach-4-tabulation-space-optimization\" style=\"\">Approach 4: Tabulation (Space Optimization)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#19-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#20-detailed-steps\" style=\"\">Detailed Steps<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#21-code-with-comments\" style=\"\">Code (with comments)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#22-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#23-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#24-summary-table\" style=\"\">Summary Table<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/minimum-path-sum\/#25-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-approach-1-recursion-brute-force\">Approach 1: Recursion (Brute Force)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Imagine you need to get to a particular cell&nbsp;<code>(i, j)<\/code>. There are only two ways:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Coming from&nbsp;<strong>above<\/strong>&nbsp;<code>(i-1, j)<\/code><\/li>\n\n\n\n<li>Coming from&nbsp;<strong>left<\/strong>&nbsp;<code>(i, j-1)<\/code><\/li>\n<\/ul>\n\n\n\n<p>So, for each cell, the minimum path sum is its own value plus the minimum path sum to&nbsp;<strong>either<\/strong>&nbsp;its top or left neighbor. Keep repeating this logic till you reach the top-left cell (base case), which is the start. If you move out of the grid (i.e.,&nbsp;<code>i &lt; 0<\/code>&nbsp;or&nbsp;<code>j &lt; 0<\/code>), return infinity so as not to consider invalid paths.<\/p>\n\n\n\n<p>This approach explores&nbsp;<strong>all<\/strong>&nbsp;possible down and right paths recursively, always aggregating the minimum sum.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-steps\">Detailed Steps<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Base case: When you reach the starting cell&nbsp;<code>(0, 0)<\/code>, just return its value (<code>grid<\/code>).<\/li>\n\n\n\n<li>Out of bounds: Return infinity if&nbsp;<code>i &lt; 0<\/code>&nbsp;or&nbsp;<code>j &lt; 0<\/code>.<\/li>\n\n\n\n<li>Recursive step: For every cell&nbsp;<code>(i, j)<\/code>, compute:\n<ul class=\"wp-block-list\">\n<li><code>up = solve(i-1, j, grid)<\/code><\/li>\n\n\n\n<li><code>left = solve(i, j-1, grid)<\/code><\/li>\n\n\n\n<li>The answer for&nbsp;<code>(i, j)<\/code>&nbsp;is&nbsp;<code>grid[i][j] + min(up, left)<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code-with-comments\">Code (with comments)<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, i, j, grid):\n        # Base case: reached start of grid\n        if i == 0 and j == 0:\n            return grid[0][0]\n        # Out of grid bounds: not allowed, return infinity\n        if i &lt; 0 or j &lt; 0:\n            return float(&quot;inf&quot;)\n        # Path sum if coming from above\n        up = self.solve(i - 1, j, grid)\n        # Path sum if coming from left\n        left = self.solve(i, j - 1, grid)\n        # Current cell's value plus minimum path from above or left\n        return grid[i][j] + min(up, left)\n\n    def minPathSum(self, grid: List[List[int]]) -&gt; int:\n        r = len(grid)\n        c = len(grid[0])\n        # Start from bottom-right cell (goal)\n        return self.solve(r - 1, c - 1, grid)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: reached start of grid<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Out of grid bounds: not allowed, return infinity<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Path sum if coming from above<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        up = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j, grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Path sum if coming from left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i, j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Current cell&#39;s value plus minimum path from above or left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[i][j] + <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(up, left)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        r = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        c = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Start from bottom-right cell (goal)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(r - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, c - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Recursively explores every possible path to the bottom-right, always trying both directions and returning the minimum sum. It uses infinity to block off-going moves out of the grid, so only valid paths count.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>&nbsp;O(2^(m+n))<br>Each cell can branch into up to two recursive calls (up and left), forming an exponential tree.<\/li>\n\n\n\n<li><strong>Space:<\/strong>&nbsp;O(m + n)<br>The recursion stack depth is at most&nbsp;<code>m + n<\/code>&nbsp;(the path length).<\/li>\n<\/ul>\n\n\n\n<p><em>Simplified:<\/em>&nbsp;Exponential time and linear space&nbsp;<em>(not practical for large grids).<\/em><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-approach-2-memoization-top-down-dp\">Approach 2: Memoization (Top-Down DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-intuition\">Intuition<\/h3>\n\n\n\n<p>The brute force recursion repeats much work, subpaths to the same cell from different directions are computed over and over.&nbsp;<strong>Memoization<\/strong>&nbsp;fixes this by storing the minimum path sum for each&nbsp;<code>(i, j)<\/code>&nbsp;in a DP array the first time it\u2019s computed, then looking it up for every subsequent request.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-detailed-steps\">Detailed Steps<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use a 2D array&nbsp;<code>dp<\/code>&nbsp;initialized to -1.<\/li>\n\n\n\n<li>If dp[i][j] is already computed (not -1), just return it, no need to recalculate.<\/li>\n\n\n\n<li>Otherwise, compute it as in recursion, store, and return.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-code-with-comments\">Code (with comments)<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, i, j, grid, dp):\n        # Base case: starting cell\n        if i == 0 and j == 0:\n            return grid[0][0]\n        # Out of bounds, treat as infinite sum so won't be chosen\n        if i &lt; 0 or j &lt; 0:\n            return float(&quot;inf&quot;)\n        # If already computed, reuse\n        if dp[i][j] != -1:\n            return dp[i][j]\n        # Try coming from above and left\n        up = self.solve(i - 1, j, grid, dp)\n        left = self.solve(i, j - 1, grid, dp)\n        # Record and return minimum path sum to (i, j)\n        dp[i][j] = grid[i][j] + min(up, left)\n        return dp[i][j]\n\n    def minPathSum(self, grid: List[List[int]]) -&gt; int:\n        r = len(grid)\n        c = len(grid[0])\n        dp = [[-1 for _ in range(c)] for _ in range(r)]\n        return self.solve(r - 1, c - 1, grid, dp)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">j<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">dp<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: starting cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Out of bounds, treat as infinite sum so won&#39;t be chosen<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> j &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># If already computed, reuse<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[i][j] != -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[i][j]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try coming from above and left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        up = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, j, grid, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(i, j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Record and return minimum path sum to (i, j)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[i][j] = grid[i][j] + <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(up, left)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[i][j]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        r = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        c = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(c)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(r)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(r - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, c - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, grid, dp)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Adds a 2D DP matrix to cache results per cell. Whenever a subproblem (cell&nbsp;<code>(i, j)<\/code>) is solved, its answer is stored for fast future lookups, eliminating redundant computation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>&nbsp;O(r * c)<br>Each cell is solved only once, so total number of subproblems = number of cells.<\/li>\n\n\n\n<li><strong>Space:<\/strong>&nbsp;O(r * c) (DP array) + O(r + c) (recursion stack).<\/li>\n<\/ul>\n\n\n\n<p><em>Simplified:<\/em>&nbsp;Linear in grid size&nbsp;<em>O(r * c)<\/em>&nbsp;for both time and space.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"12-approach-3-tabulation-bottom-up-dp\">Approach 3: Tabulation (Bottom-Up DP)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of recursion,&nbsp;<strong>tabulation<\/strong>&nbsp;builds up the answer iteratively from the start, using a 2D DP table.<br>At each cell&nbsp;<code>(i, j)<\/code>, the minimum path sum is its own value plus the minimum of:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The cell&nbsp;<strong>above<\/strong>&nbsp;(<code>dp[i-1][j]<\/code>)<\/li>\n\n\n\n<li>The cell&nbsp;<strong>to the left<\/strong>&nbsp;(<code>dp[i][j-1]<\/code>)<\/li>\n<\/ul>\n\n\n\n<p>Handle the first row and column carefully, as they only have one direction available (left or up).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-detailed-steps\">Detailed Steps<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Set&nbsp;<code>dp = grid<\/code><\/li>\n\n\n\n<li>For all cells&nbsp;<code>(i, j)<\/code>, fill the value from top and left neighbors<\/li>\n\n\n\n<li>Use&nbsp;<code>float(\"inf\")<\/code>&nbsp;for out-of-bounds neighbors<\/li>\n\n\n\n<li>Final result is&nbsp;<code>dp[r-1][c-1]<\/code><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-code-with-comments\">Code (with comments)<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def minPathSum(self, grid: List[List[int]]) -&gt; int:\n        r = len(grid)\n        c = len(grid[0])\n        dp = [[-1 for _ in range(c)] for _ in range(r)]\n        dp[0][0] = grid[0][0]  # Start cell\n        for i in range(0, r):\n            for j in range(0, c):\n                if i == 0 and j == 0:\n                    continue  # Skip start cell\n                # If no row above, set up = inf; else, use value above\n                if i == 0:\n                    up = float(&quot;inf&quot;)\n                else:\n                    up = dp[i - 1][j]\n                # If no col to left, set left = inf; else, use value to left\n                if j == 0:\n                    left = float(&quot;inf&quot;)\n                else:\n                    left = dp[i][j - 1]\n                # Current cell = its value + min path sum from up or left\n                dp[i][j] = grid[i][j] + min(up, left)\n        return dp[r - 1][c - 1]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        r = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        c = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(c)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(r)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Start cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, r):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, c):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">continue<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Skip start cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># If no row above, set up = inf; else, use value above<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    up = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    up = dp[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][j]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># If no col to left, set left = inf; else, use value to left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    left = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    left = dp[i][j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Current cell = its value + min path sum from up or left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                dp[i][j] = grid[i][j] + <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(up, left)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[r - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][c - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>A DP grid is built row by row, always adding the grid value to the minimum from the previous row or column. Edges are handled using infinity to avoid picking out-of-bounds sums.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>&nbsp;O(r * c)<br>Each grid cell is filled exactly once.<\/li>\n\n\n\n<li><strong>Space:<\/strong>&nbsp;O(r * c)<br>Due to the 2D DP table.<\/li>\n<\/ul>\n\n\n\n<p><em>Simplified:<\/em>&nbsp;Linear in the grid size for both time and space.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"18-approach-4-tabulation-space-optimization\">Approach 4: Tabulation (Space Optimization)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-intuition\">Intuition<\/h3>\n\n\n\n<p>At any step, to fill the value for the current cell, we&nbsp;<strong>only need<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The value directly to the left (in the current row)<\/li>\n\n\n\n<li>The value right above (from the previous row)<\/li>\n<\/ul>\n\n\n\n<p>This means we can store results for a single previous row (and the current row we&#8217;re computing) rather than the whole matrix, reducing the space from O(r * c) to O(c).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-detailed-steps\">Detailed Steps<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use two 1D arrays:&nbsp;<code>prev<\/code>&nbsp;(previous row) and&nbsp;<code>curr<\/code>&nbsp;(current row).<\/li>\n\n\n\n<li>For each row, build&nbsp;<code>curr<\/code>&nbsp;left-to-right using only&nbsp;<code>prev<\/code>&nbsp;and itself.<\/li>\n\n\n\n<li>After each row, update&nbsp;<code>prev = curr<\/code>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"21-code-with-comments\">Code (with comments)<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def minPathSum(self, grid: List[List[int]]) -&gt; int:\n        r = len(grid)\n        c = len(grid[0])\n        prev = [0] * c  # Previous row's DP\n        for i in range(0, r):\n            curr = [0] * c  # Current row's DP\n            for j in range(0, c):\n                # Start cell\n                if i == 0 and j == 0:\n                    curr[0] = grid[0][0]\n                    continue\n                # Value from the cell above (prev row, same col)\n                if i == 0:\n                    up = float(&quot;inf&quot;)\n                else:\n                    up = prev[j]\n                # Value from the left (current row, prev col)\n                if j == 0:\n                    left = float(&quot;inf&quot;)\n                else:\n                    left = curr[j - 1]\n                curr[j] = grid[i][j] + min(up, left)\n            prev = curr  # Move current row to prev\n        return prev[c - 1]  # Last cell of last row\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">grid<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        r = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        c = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * c  <\/span><span style=\"color: #6A9955\"># Previous row&#39;s DP<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, r):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            curr = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * c  <\/span><span style=\"color: #6A9955\"># Current row&#39;s DP<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, c):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Start cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    curr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = grid[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Value from the cell above (prev row, same col)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    up = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    up = prev[j]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Value from the left (current row, prev col)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> j == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    left = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    left = curr[j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                curr[j] = grid[i][j] + <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(up, left)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = curr  <\/span><span style=\"color: #6A9955\"># Move current row to prev<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev[c - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Last cell of last row<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"22-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>Uses only two arrays to capture the rolling DP values, significantly reducing space without loss of clarity or correctness.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"23-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>&nbsp;O(r * c)<br>Every element visited once.<\/li>\n\n\n\n<li><strong>Space:<\/strong>&nbsp;O(1)<br>Only two rows of data are ever kept at once.<\/li>\n<\/ul>\n\n\n\n<p><em>Simplified:<\/em>&nbsp;Time O(r * c), Space O(c), optimal for big grids.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"24-summary-table\">Summary Table<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Notes<\/th><\/tr><\/thead><tbody><tr><td>Recursion (Brute Force)<\/td><td>O(2^(r+c))<\/td><td>O(r + c)<\/td><td>Educational, not optimal<\/td><\/tr><tr><td>Memoization (Top-Down DP)<\/td><td>O(r * c)<\/td><td>O(r * c)<\/td><td>Fast, clear with DP cache<\/td><\/tr><tr><td>Tabulation (Bottom-Up DP)<\/td><td>O(r * c)<\/td><td>O(r * c)<\/td><td>Systematic, robust<\/td><\/tr><tr><td>Tabulation (Space Optimized)<\/td><td>O(r * c)<\/td><td>O(1)<\/td><td>Best for large grids<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"25-conclusion\">Conclusion<\/h2>\n\n\n\n<p>&#8220;Minimum Path Sum&#8221; is a fundamental grid DP problem. Mastering all these approaches builds up both your coding skill and your DP intuition. Start with recursion for the concept, then use memoization or iterative tabulation, and for large grids, always remember to optimize your space. Keep practicing, and soon you&#8217;ll be confident with any grid-based dynamic programming challenge!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;m x n&nbsp;grid&nbsp;filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Here&#8217;s the [Problem Link] to begin with. Note:&nbsp;You can only move either down or right at any point in time. Example 1: Input: grid = [[1,3,1],[1,5,1],[4,2,1]]Output: 7Explanation: Because the<\/p>\n","protected":false},"author":1,"featured_media":829,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[38,19],"class_list":{"0":"post-826","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-dynamic-programming-on-2d-arrays","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/minimum-path-sum-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/826","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=826"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/826\/revisions"}],"predecessor-version":[{"id":833,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/826\/revisions\/833"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/829"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=826"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=826"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=826"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}