?
代碼展示：
?dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
?該題可以通過動態(tài)規(guī)劃解決，動態(tài)規(guī)劃的題根據(jù)以下的5大步驟便可輕松解決
? ? ? ? 1.狀態(tài)表示
? ? ? ? ? ? ? ? 題目要求我們計算從起點到最后一個位置的最小路徑和，我們可以創(chuàng)建一個dp表，dp【i】【j】表示從起點到【i，j】位置的最小路徑和
? ? ? ? 2.狀態(tài)轉(zhuǎn)移方程
? ? ? ? ? ? ? ? 我們從最近的一步開始分析，我們有兩種方法可以到達(dá)【i，j】位置，要么從【i-1，j】位置向下移動，要么從【i，j-1】位置向右移動，我們要如何選擇呢，由于我們需要求出的是最小路徑和，所以我們可以比較到達(dá)【i-1，j】和【i，j-1】的最小路徑和，即dp【i-1，j】和dp【i，j-1】,從較小的那個位置出發(fā)到【i，j】位置即加上【i，j】位置的數(shù)值，便是【i，j】的最小路徑和，所以我們可以得到狀態(tài)轉(zhuǎn)移方程：?dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
? ? ? ? 3.初始化
? ? ? ? ? ? ? ? 我們可以通過增加輔助結(jié)點的方式來輔助初始化，在該題中我們創(chuàng)建的dp數(shù)值相比于grid數(shù)組，我們要多加一行一列，而此時我們要注意，
????????（1）.輔助結(jié)點中添加的值要保證后續(xù)的數(shù)據(jù)添加是正確的，根據(jù)對該題的分析，我們需要將第一行和第一列除了[0,1]位置和[1.0]位置，其他位置都設(shè)為int數(shù)據(jù)的最大值
? ? ? ? （2）.下標(biāo)的映射關(guān)系，此時由于添加了一行一列，所以dp[i][j]對應(yīng)grid[i-1][j-1]
? ? ? ? 4.填充數(shù)組
? ? ? ? ? ? ? ? 根據(jù)狀態(tài)轉(zhuǎn)移方程填充數(shù)組
? ? ? ? 5，返回值文章來源：http://www.zghlxwxcb.cn/news/detail-545668.html
? ? ? ? ? ? ? ? 終點位置是【m，n】,所以要返回dp[m][n]文章來源地址http://www.zghlxwxcb.cn/news/detail-545668.html
到了這里，關(guān)于Java 動態(tài)規(guī)劃 64. 最小路徑和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
