设平面上有一个m×n 的网格，将左下角的网格点标记为（0,0）而右上角的网格点标记为（m,n）。某人想从（0,0）出发沿网格线行进到达（m,n），但是在网格点（i,j）处他只能向上行进或者向右行进，向上行进的代价为aij（amj ＝＋∞），向右行进的代价是bij（bin ＝＋∞）。试设计一个动态规划算法，在这个网格中为该旅行者寻找一条代价最小的旅行路线。
import java.util.*;
import static java.lang.Math.*;
public class Shiyaner
{
public static void main(String[] args)
{
final int m = 5;
final int n = 5;
// 定义向上，向右的代价，以及最优代价
int[][] Cost = new int[m+1][n+1];
int[][] Down = new int[m][n+1];
int[][] Right = new int[m+1][n];
int count = 0, i = 0, j = 0;
// 随机的产生向上代价数组Above，并输出
for(i = 0; i < m; i++)
for(j = 0; j < n+1; j++)
{
Random rand = new Random();
Down[i][j] = (rand.nextInt(5)+5);
}
System.out.printf("Down:\n");
for(i = 0; i < m; i++)
{
for(j = 0; j < n+1; j++)
{
System.out.printf("%5d", Down[i][j]);
}
System.out.println("\n");
}
// 随机的产生向右代价数组Right，并输出
for(i = 0; i < m+1; i++)
for(j = 0; j < n; j++)
{
Random rand = new Random();
Right[i][j] = (rand.nextInt(5)+5);
}
System.out.printf("Right:\n");
for(i = 0; i < m+1; i++)
{
for(j = 0; j < n; j++)
{
System.out.printf("%5d", Right[i][j]);
}
System.out.println("\n");
}
// 求出最优代价数组Cost并输出
Cost[0][0] = 0;
for(i = 1; i < m+1; i++)
Cost[i][0] = Cost[i-1][0] + Down[i-1][0];
for(j = 1; j < n+1; j++)
Cost[0][j] = Cost[0][j-1] + Right[0][j-1];
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
Cost[i+1][j+1] = min((Cost[i+1][j] + Right[i+1][j]), (Cost[i][j+1] +
Down[i][j+1]));
System.out.printf("最优距离:\n");
for(i = 0; i < m+1; i++)
{
for(j = 0; j < n+1; j++)
{
System.out.printf("%5d",Cost[i][j]);
}
System.out.println("\n");
}
// 输出最优路径的具体走法
System.out.println("请输入你想到达的坐标位置：");
Scanner in1 = new Scanner(System.in);
System.out.print("横坐标：");
int a = in1.nextInt();
System.out.print("纵坐标：");
int b = in1.nextInt();
int[] d = new int[a+b];
int k = a+b-1;
i = a - 1 ;
j = b - 1 ;
while ( i != 0 && j != 0 )
{
if ( Cost[i+1][j+1] == (Cost[i+1][j] + Right[i+1][j]))
{
d[k] = 0;
j--;
k--;
}
else
{
d[k] = 1;
i--;
k--;
}
}
if( i == 0 )
{
while ( j != 0 )
{
d[k] = 1;
j--;
k--;
}
}
if( j == 0 )
{
while ( i != 0 )
{
d[k] = 0;
i--;
k--;
}
}
for (i = a+b-1 ; i >= 0 ; i-- )
{
if ( d[i] == 0 )
System.out.println("Right");
else
System.out.println("Down");
}
}
}
运行结果如下：
Down:
5 9 7 6 5 6
8 9 8 5 7 6
9 6 7 9 6 5
9 9 7 5 6 6
5 7 5 9 5 5
Right:
7 7 9 8 8
6 6 5 6 6
8 9 7 9 8
9 7 7 5 8
6 7 7 9 7
6 7 8 5 6
最优距离:
0 7 14 23 31 39
5 11 17 22 28 34
13 20 25 27 35 40
22 26 32 36 41 45
31 35 39 41 47 51
36 42 44 50 52 56
请输入你想到达的坐标位置：
横坐标：3
纵坐标：3
Down
Down
Down
Down
Right
Right
定义dp[i][j]表示从左下角到(i, j)的最小代价，a[i][j]表示向上行进的代价，b[i][j]表示向右行进的代价。
很显然，想要到达dp[i][j] 无非就是从dp[i - 1][j]向上走，或者从dp[i][j - 1]向右走，很容易写出状态转移方程如下
dp[i][j] = min(dp[i - 1][j] + a[i - 1][j], dp[i][j - 1] + b[i][j - 1])
至于路线和dp优化，自己补上吧，已经不是什么难事了。
public int minPathSum(int[][] a, int [][] b) {
int m = a.length, n = a[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 0;
for (int i = 1; i < m; i++) {
dp[i][0] = a[i - 1][0] + dp[i - 1][0];
}
for (int i = 1; i < n; i++) {
dp[0][i - 1] = b[0][i - 1] + dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j] + a[i - 1][j], dp[i][j - 1] + b[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}