【LeetCode】 542. 01 矩阵动态规划 dp

怼烎@ 2021-06-10 20:38 340阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

这道题目的解法有两种，对于广度优先来说我实在不是很了解，所以只能说一下动态规划的算法了

这道题目需要找到的是最优子结构，递推式如下  
![在这里插入图片描述][20200415203118671.png]

1.  我们能很明确的得出，某个点的最小值即为其 上、左、下、右 四个值中的最小值，所以，可以考虑用dp来做
2.  但是遇到问题，因为0所在的位置不清楚，所以需要从四个方向（左上角、左下角、右上角、右下角）来进行dp，不过仔细思考会发现，只做对角线就可以，其实这一点还是比较不容易思考出来的，
3.  我是这样思考的，从 `左上角` 开始向下dp时，只要某个值的 `左方` 和 `上方` 有0，那么，这个点的距离，就是 `左方` 和 `上方` 正确dp的值，此时这个点还需要 `右方` 和 `下方` dp的值  
    ![在这里插入图片描述][20200415203949471.png]
4.  于是，再从 `右下角` 重复一次，获取 `下方` 和 `右方` dp的值即可  
    ![在这里插入图片描述][20200415204035536.png]

### code ###

class Solution { 
        public int[][] updateMatrix(int[][] matrix) { 
    		int rows = matrix.length;
    		int cols = matrix[0].length;
    		int[][] dp = new int[rows][cols];
    		for (int i = 0; i < rows; i++) { 
    			for (int j = 0; j < cols; j++) { 
    				dp[i][j] = matrix[i][j] == 0 ? 0 : 1;
    			}
    		}
    
    		for (int i = 0; i < rows; i++) { 
    			for (int j = 0; j < cols; j++) { 
    				if (i - 1 >= 0) { 
    					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
    				}
    				if (j - 1 >= 0) { 
    					dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
    				}
    			}
    		}
    
    		for (int i = rows - 1; i >= 0; i--) { 
    			for (int j = cols - 1; j >= 0; j--) { 
    				if (i + 1 < rows) { 
    					dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
    				}
    				if (j + 1 < cols) { 
    					dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
    				}
    			}
    		}
    
    		return dp;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/01-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/c365ec7a6134478190ea63a800e48771.png
[20200415203118671.png]: /images/20210529/91a025de828c4f2882e50870f25d1b6f.png
[20200415203949471.png]: /images/20210529/d577bf2967b345ebbfb1f67da26e0b81.png
[20200415204035536.png]: /images/20210529/966f1477598648659caa919f488e5605.png