现有一个地图,由横线与竖线组成(参考围棋棋盘),且两点之间有行走距离起点为左上角,终点为右下角在地图上,每次行走只能沿线移动到临近的点,并累加路径计算一个人从地图的起点走到终点的最小路径为多少。
m*n地图表示如下:
3
3
1 3 4
2 1 2
4 3 1
其中m=3,n=3 表示3*3的矩阵
行走路径为:下>右>右>下
路径总长:1+2+1+2+1=7
1 2 1 2
3
2 3 9 8 6 2 3 7
21
地图参数为:
1
2
1 2
m=1,n=2,表示1*2的矩阵,最短距离是左>右
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(br.readLine().trim()); int n = Integer.parseInt(br.readLine().trim()); int[][] grid = new int[m][n]; for(int i = 0; i < m; i++){ String[] row = br.readLine().trim().split(" "); for(int j = 0; j < n; j++) grid[i][j] = Integer.parseInt(row[j]); } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(i == 0 && j == 0) grid[i][j] = grid[i][j]; else if(i == 0) grid[i][j] += grid[i][j - 1]; // 上边界只能从左边过来 else if(j == 0) grid[i][j] += grid[i - 1][j]; // 左边界只能从上边过来 else // 选择两种方案中路径小的 grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } System.out.println(grid[m - 1][n - 1]); } }
#include<stdio.h> int min(int a,int b) {return a>b?b:a;} int main(){ int m,n,i,j; int arr[1005][1005]; scanf("%d",&m); scanf("%d",&n); for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%d",&arr[i][j]);//初始化 } } int dp[1005][1005];//dp数组用来存每一个位置最小数字和 for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(i==0&&j==0)//第一个位置就是本身 dp[i][j]=arr[i][j]; else if(i==0&&j!=0)//只有一行 dp[i][j]=dp[i][j-1]+arr[i][j]; else if(i!=0&&j==0)//只有一列 dp[i][j]=dp[i-1][j]+arr[i][j]; else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j];//状态转移方程 } } printf("%d",dp[m-1][n-1]); return 0; }
import java.util.Scanner; public class Main { // 分析: 从左往右的尝试 public static void main(String[] args) { Scanner in = new Scanner(System.in); int row = in.nextInt(); int col = in.nextInt(); int[][] array = new int[row][col]; in.nextLine(); for (int i = 0; i < row; i++) { String[] numbers = in.nextLine().split(" "); for (int j = 0; j < col; j++) { array[i][j] = Integer.parseInt(numbers[j]); } } System.out.println(process1(array, row, col, 0, 0)); System.out.println(process2(array)); System.out.println(process3(array)); } // 暴力递归. 返回值表示从当前位置出发,到结束时,最小的路径. private static int process1(int[][] array, int row, int col, int i, int j) { if (i == row - 1 && j == col - 1) { // 终止位置 return array[i][j]; } if (i == row - 1) { // 最后一行,非终止位置 return array[i][j] + process1(array, row, col, i, j + 1); } if (j == col - 1) { // 最后一列,非终止位置 return array[i][j] + process1(array, row, col, i + 1, j); } // 中间,取朝右或者朝下中较小值,在加上当前值 return Math.min(process1(array, row, col, i, j + 1), process1(array, row, col, i + 1, j)) + array[i][j]; } // 记忆化搜索,动态规划 private static int process2(int[][] array) { int row = array.length; int col = array[0].length; int[][] dp = new int[row][col]; dp[row - 1][col - 1] = array[row - 1][col - 1]; for (int j = col - 2; j >= 0; j--) { dp[row - 1][j] = array[row - 1][j] + dp[row - 1][j + 1]; } for (int i = row - 2; i >= 0; i--) { dp[i][col - 1] = array[i][col - 1] + dp[i + 1][col - 1]; } for (int i = row - 2; i >= 0; i--) { for (int j = col - 2; j >= 0; j--) { dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) + array[i][j]; } } return dp[0][0]; } // 直接修改原数组,从右往左,由下到上推结果. 动态规划 private static int process3(int[][] array) { int row = array.length; int col = array[0].length; for (int j = col - 2; j >= 0; j--) { array[row - 1][j] += array[row - 1][j + 1]; } for (int i = row - 2; i >= 0; i--) { array[i][col - 1] += array[i + 1][col - 1]; } for (int i = row - 2; i >= 0; i--) { for (int j = col - 2; j >= 0; j--) { array[i][j] += Math.min(array[i][j + 1], array[i + 1][j]); } } return array[0][0]; } }
import java.util.*; public class Main { static int [][] dx={{1,0},{0,1},{0,-1},{-1,0}}; public static void main(String [] args){ Scanner sc =new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int [] [] nums=new int[n][m]; int sum=0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { nums[i][j]=sc.nextInt(); sum+=nums[i][j]; } } boolean[][]visited=new boolean[n][m]; visited[0][0]=true; System.out.println(dfs(0,0,n-1,m-1,visited,nums,sum)); } private static int dfs(int x, int y, int tx, int ty, boolean[][] visited,int [][]nums,int sum) { if (x==tx&&y==ty){ return nums[tx][ty]; } int res=sum; for (int i = 0; i < 4; i++) { int curx=dx[i][0]+x; int cury=dx[i][1]+y; if (isin(curx,cury,tx,ty)&&!visited[curx][cury]){ visited[curx][cury]=true; res=Math.min(res,dfs(curx,cury,tx,ty,visited,nums,sum)+nums[x][y]); visited[curx][cury]=false; } } return res; } private static boolean isin(int curx, int cury, int tx, int ty) { return curx>=0&&curx<=tx&&cury>=0&&cury<=ty; } }
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] mapp = new int[n][m]; for(int i = 0; i < n ;i++){ for(int j = 0; j < m; j++){ mapp[i][j] = sc.nextInt(); } } int[][] dp = new int[n][m]; dp[0][0] = mapp[0][0]; for(int i = 0; i < n ;i++){ for(int j = 0; j < m; j++){ if(i == 0 && j != 0 ) dp[i][j] = dp[i][j - 1] + mapp[i][j]; else if(i != 0 && j == 0) dp[i][j] = dp[i - 1][j] + mapp[i][j]; else if(i != 0 && j != 0) dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + mapp[i][j]; } } System.out.println(dp[n - 1][m - 1]); } }java 题解
m=int(input().strip()) n=int(input().strip()) M=[] for i in range(m): M.append(list(map(int,input().strip().split()))) dp=[[0]*(n) for _ in range(m)] for i in range(m): for j in range(n): if i-1>=0: up=dp[i-1][j]+M[i][j] else:up=dp[i][j-1]+M[i][j] if j-1>=0: left=dp[i][j-1]+M[i][j] else:left=dp[i-1][j]+M[i][j] dp[i][j]=min(up,left); print(dp[-1][-1])
m = int(raw_input()) n = int(raw_input()) matrix = [[0 for _ in range(n)] for _ in range(m)] for i in range(m): line = raw_input().split(' ') for j in range(n): matrix[i][j] = int(line[j]) dp = [[0 for _ in range(n)] for _ in range(m)] # dp[i][j] means the min val when arrive at matrix[i][j] dp[0][0] = matrix[0][0] for i in range(1, m): dp[i][0] = dp[i - 1][0] + matrix[i][0] for j in range(1, n): dp[0][j] = dp[0][j - 1] + matrix[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j] print dp[m - 1][n - 1]