需求：
有二维数组，例如：
{5,2,6,3}
{1,4,8,1}
{3,2,6,3}
{9,3,7,2}
每个数字代表代表一条路，数字是路的长度。
求从左上角走到右下角，最短距离是多少？ 每次只能向右或向下走，不能往上或往左走。
我们使用动态规划如何求解？
在求解这个问题时，动态规划的思想是从终点开始，不断向前递推，把问题的子问题一步一步解决，并存储结果，以便重复使用。
假设 dp[i][j] 表示从左上角（0，0）走到（i，j）的最短距离，则可以得到转移方程：
dp[i][j]=min(dp[i-1][j], dp[i][j-1]) + a[i][j]
最终答案为 dp[m-1][n-1]，其中 m 和 n 分别是二维数组的行数和列数。
/**
* 动态规划算法求解 A点到B点最小距离
*/
public class DongTaiGuiHua_MinDist {
public static void main(String[] args) {
int[][] arr = {
{5,2,6,3},
{1,4,8,1},
{3,2,6,3},
{9,3,7,2}
};
/* 推导数组结果
int[][] arr ={
{5,7,13,16},
{6,10,18,19},
{9,11,17,20},
{18,14,21,22}
}*/
System.out.println("动态规划计算最小距离:" + minDist(arr,arr.length, arr[0].length));
}
public static int minDist(int[][] arr, int n, int m) {
//初始化第一列数据
for(int i=1; i<n; i++) {
arr[i][0] = arr[i-1][0] + arr[i][0];
}
//初始化第一行数据
for(int j=1; j<m; j++) {
arr[0][j] = arr[0][j-1] + arr[0][j];
}
//动态规划求解
for(int i=1; i<n; i++) {
for(int j=1; j<m; j++) {
arr[i][j] = arr[i][j] + Math.min(arr[i-1][j],arr[i][j-1]);
}
}
return arr[n-1][m-1];
}
}
根据动态规划的解决思路，我们这里列出来数组推到过程中的值：
推导数组结果
int[][] arr ={
{5,7,13,16},
{6,10,18,19},
{9,11,17,20},
{18,14,21,22}
}