【问题描述】
如图所示的矩形图中找到一条从左下角到右上角的最短路径，图中数字表示边的长度。只能向右或向上走。
【输入文件】第一行两个数，N M，矩形的点有N行M列。（0<N，M<1000）接下来N行每行M-1个数描述横向边的长度。接下来N-1行每行M个数描述纵向边的长度。边的长度小于10。
【输出文件】一个数——最短路径长度。
【输入样例】
4 5
3 7 4 8
4 6 3 5
3 6 3 5
5 4 6 2
7 6 3 5 3
2 8 5 9 4
8 7 4 3 7
【输出样例】
28
【问题分析】
因为只能向右或向上走，所以阶段应该是这样的：
我的做法：
把数据放到新的数组中：
如图：
红色标出的是每一个中点，求出每一个点的最小值，从左下角到右上角，求出最上角的最小值，及为最优值。
Java程序如下
import java.util.Scanner;
public class JieDao {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = 2 * input.nextInt() - 1;
int m = 2 * input.nextInt() - 1;
int[][] a = new int[n][m];
for (int i = 0; i < n; i += 2) {
for (int j = 1; j < m; j += 2) {
a[i][j] = input.nextInt();
}
}
for (int i = 1; i < n; i += 2) {
for (int j = 0; j < m; j += 2) {
a[i][j] = input.nextInt();
}
}
input.close();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
getMin(a, n, m);
}
public static void getMin(int[][] a, int n, int m) {
int i = n - 3;
int j = 0;
int ti;
int tj;
while (a[0][m - 1] == 0) {
ti = i;
tj = j;
while (i < n && j < m && i >= 0 && j >= 0) {
if (i == 0 && j == 0) {
a[i][j] = a[i + 2][j] + a[i + 1][j];
} else if (i == (n - 1)) {
a[i][j] = a[i][j - 2] + a[i][j - 1];
} else if (j == 0) {
a[i][j] = a[i + 2][j] + a[i + 1][j];
} else {
a[i][j] = a[i + 2][j] + a[i + 1][j] > a[i][j - 2]
+ a[i][j - 1] ? a[i][j - 2] + a[i][j - 1]
: a[i + 2][j] + a[i + 1][j];
}
i += 2;
j += 2;
}
if (ti == 0) {
j = tj + 2;
i = 0;
} else if (tj == 0) {
i = ti - 2;
j = 0;
}
}
System.out.println(a[0][m - 1]);
}
}
在网上找到的：
这样想就是上面说的数塔问题了，只不过数塔问题的数在点上而街道问题的数在边上。但是并不影响问题的求解我们可以用数塔问题的思路来解这个问题。
设计一个二维状态opt[i,j]表示走到（i,j）的最短路径，显然这个路径只可能是左边或上边走来的，所以决策就是这两个方向上加上经过的边的和中一个较短的路。于是有下面的状态转移方程：
opt[i+1,j]+z[i,j] (j=1)
opt[i,j]＝ opt[i,j-1]+h[i,j] (i=n)
min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]} (0<i<=n,0<j<=m)
和数塔问题一样，这个问题也可以做类似的预处理：初始化opt的值是一个很大的数，保证解不会超过他，但要注意不要太大了，太大了可能有２２５问题。opt[0,0]=0。这样就可以把方程整理为：
opt[i,j]= min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]}
复杂度：状态数O（N2）*转移代价O（1）=O（N2）。
这一类问题是很经典的问题。
思考这样一个问题：如果让找出一条最短路径，一条较短路径，且两条路径不重合该怎么办呢？
这个问题先留给大家思考，在后面的多维状态中会详细的讲。
#include <iostream>
using namespace std;
#define MAXN 1001
int row[MAXN][MAXN];
int col[MAXN][MAXN];
int g[MAXN][MAXN];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int n,m,i,j;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<m-1;j++)
{
scanf("%d",&row[i][j]);
g[i][j]=0;
}
for(i=0;i<n-1;i++)
for(j=0;j<m;j++)
scanf("%d",&col[i][j]);
for(i=1;i<m;i++) //最下面一行
g[n-1][i]=g[n-1][i-1]+row[n-1][i-1];
for(i=n-2;i>=0;i--) //最左边一列
g[i][0]=g[i+1][0]+col[i][0];
for(i=n-2;i>=0;i--)
for(j=1;j<m;j++)
{
g[i][j]=min(g[i][j-1]+row[i][j-1],g[i+1][j]+col[i][j]);
}
printf("%d\n",g[0][m-1]);
}
return 0;
}
#include<iostream>
#define Min(a,b) a<b?a:b
#define MAXN 1010
#define inf 1000000
int h[MAXN][MAXN],z[MAXN][MAXN],a[MAXN][MAXN],dp[MAXN][MAXN];
using namespace std;
int main(){
int i,j,n,m,min;
while(~scanf("%d%d",&n,&m)){
for(i=1;i<=n;i++)
for(j=2;j<=m;j++)
scanf("%d",&h[i][j]);
for(i=1;i<n;i++)
for(j=1;j<=m;j++)
scanf("%d",&z[i][j]);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
dp[i][j]=0;
dp[n][0]=0;
dp[n][1]=h[n][1];
for(i=2;i<=m;i++)
dp[n][i]=dp[n][i-1]+h[n][i];
for(i=n-1;i>0;i--)
for(j=1;j<=m;j++)
if(j==1)
dp[i][j]=dp[i+1][j]+z[i][j];
else
dp[i][j]=Min(dp[i+1][j]+z[i][j],dp[i][j-1]+h[i][j]);
printf("%d\n",dp[1][m]);
}
return 0;
}