【阿里云在线编程】 34.矩阵最小路径和

水深无声 2021-06-10 20:38 357阅读 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> ##

### 思路 ###

> ps：声明一个格子来存储路径条数或者路径长度都可，可以解决路径条数和长度连个问题

![在这里插入图片描述][20200228105543302.png]

1.  典型的动态规划题目，从左上角到右下角，只能向右或者向下移动，所以第一行和第一列，只有一种可能的情况  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]
2.  除了第一行或者第一列的格子，它的上一步，有可能是 `上边的格子` 或者 `左边的格子` ，所以有可能是这两种情况，所以它的路径可能性就是这两个格子，如果是路径长度的话，就取这两个格子的路径长度的最小值  
    ![在这里插入图片描述][20200228110201431.png]
3.  最后可以遍历得出每个格子的路径数量，也就能得出每个格子的最短路径数  
    ![在这里插入图片描述][20200228110415703.png]

### code ###

package solution34;
    
    class Solution { 
    
        public int solution(int[][] m) { 
            int[][] dp = new int[m.length][m[0].length];
            for (int i = 0; i < m.length; i++) { 
                for (int j = 0; j < m[0].length; j++) { 
                    if (i == 0 && j != 0)
                        dp[i][j] = m[i][j] + dp[i][j - 1];
                    else if (j == 0 && i != 0)
                        dp[i][j] = m[i][j] + dp[i - 1][j];
                    else if (j != 0 && i != 0)
                        dp[i][j] = m[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
                    else
                        dp[i][j] = m[i][j];
                }
            }
            return dp[m.length - 1][m[0].length - 1];
        }
    
    }

[Link 1]: https://developer.aliyun.com/coding/34
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/a01b26ec59194bc4a5f81f531356c649.png
[20200228105543302.png]: /images/20210529/8b08175b426a4763883a8f0f20e5df55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/cbaced0847b7416fbe82f120b4ba44c3.png
[20200228110201431.png]: /images/20210529/2b4ff4963d724d26be646d706211afd2.png
[20200228110415703.png]: /images/20210529/9aef42e90d774f16ad39572199f15cb5.png