当前位置:首页 » Project Euler » 详细页

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} $$

Solution

典型的动态规划问题。 设grid[i][j]为从左上点[0,0]达到目标点[i,j]处的最小路径和。题目中说明可以向右和向下走,那么: $$grid[i][j]+=MIN\left\{grid[i][j-1],grid[i-1][j]\right\}$$ 从左上点遍历到右下点即可。要注意四个边界上的点的最小路径和。当点[i,j]位于边界时,只可以向右(或者向左)走。例如: $$grid[2][0]+=grid[1][0]$$ $$grid[0][2]+=grid[0][1]$$

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数据的数组
		 int[][] grid = readGrid();//读入数据到二维数组grid
	     //动态规划
         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];
	 }
	 
	 public static int[][] readGrid()
	 {
		 int [][]grid=new int[80][80];
		 String[][] rows = new String[80][80];
         int index = 0;
         BufferedReader br = null;
         try {
           // 读文件了. 路径就是那个txt文件路径
            br  = new BufferedReader(new FileReader(new File("C:\\Users\\wby\\Desktop\\p081_matrix.txt")));
            String str = null;
            // 按行读取
            while((str=br.readLine())!=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