### Path sum: two ways题号：81 难度： 10 中英对照

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

$$\begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix}$$

### Code

import java.io.*;

public class p81 {
public static void main(String[] args)
{
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run()
{
// 初始化一个用于存储txt数据的数组
//动态规划
for (int i = 0; i <grid.length; i++) {
for (int j = 0; j <grid.length; j++) {
int temp;
if(i>0 && j>0)
temp=Math.min(grid[i-1][j], grid[i][j-1]);
else if(i>0)
temp=grid[i-1][j];
else if(j>0)
temp=grid[i][j-1];
else
temp=0;
grid[i][j]+=temp;
}
}
return grid[grid.length-1][grid.length-1];
}

{
int [][]grid=new int[80][80];
String[][] rows = new String[80][80];
int index = 0;
try {
// 读文件了. 路径就是那个txt文件路径
String str = null;
// 按行读取
rows[index] = str.split(",");
index++;
}
for (int i=0;i<rows.length;i++) {
for (int j=0;j<rows.length;j++) {
grid[i][j]=Integer.parseInt(rows[i][j]);
}
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return grid;
}
}

427337
12ms