동적 계획 문제: 행렬 의 최소 경로 와

제목:
n * m 의 행렬 a 를 지정 합 니 다. 왼쪽 상단 부터 매번 오른쪽으로 또는 아래로 만 갈 수 있 습 니 다. 마지막 으로 오른쪽 아래 에 있 는 위치 에 도착 합 니 다. 경로 에 있 는 모든 숫자 를 누적 하면 경로 와 모든 경 로 를 출력 하 는 가장 작은 경로 입 니 다.예제: m n 4 1 3 5 9 8 1 3 4 5 0 6 1 8 4 0 출력: 12
해법 1:
전체 행렬 의 첫 줄 과 첫 번 째 열 을 업데이트 하려 면 직접 구 하고 업데이트 하면 됩 니 다. 나머지 부분 은 행렬 이 왼쪽 이나 위 에서 만 지나 가 는 것 을 볼 수 있 습 니 다. 왼쪽 과 위의 수의 크기 를 비교 하고 작은 것 을 취하 면 됩 니 다.

public int MinPathSum1(int[][] m){
	if (m == null || m.length == 0 || m[0] == null || m[0].length = 0){
		return 0;
	}
	int row = m.length;
	int col = m[0].length;
	int [][] dp = new int [row][col];
	dp[0][0] = m[0][0];
	for (int i = 1;i < row ;i++){
		dp[i][0] = dp[i-1][0] + m[i][0];
	}
	for (int j = 1;j < col; j++){
		dp[0][j] = dp[0][j-1] + m[0][j];
	}
	for (int i = 1;i < row;i++){
		for(int j =1; j < col; j++){
			dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + m[i][j];
		}
	}
	return dp[row-1][col-1];
	

해법
해법 1 의 공간 은 압축 할 수 있다.8134 는 하나의 배열 로 만 스크롤 업 데 이 트 를 할 수 있 습 니 다.공간 을 절약 하기 위해 서 는 차원 이 작은 배열 을 선택 하여 시작 할 수 있 습 니 다.교체 과정 전 몇 걸음 1, 3, 5, 9 - > 1, 4, 9, 18 - > 9, 3, 9, 18 - > 9, 5, 9, 9, 18

public int minPathSum2(int [][] m){
	if (m == null || m.length == 0 || m[0] == null || m[0].length = 0){
		return 0;
	}	
	int more = Math.max(m.length,m[0].length);//         
	int less = Math.min(m.length, m[0].length);//         
	boolean colIsMore = more == m[0].length;//             
	int[] dp = new int[less];
	dp[0] = m[0][0];
	for (i = 1;i < less; i++){
		dp[i] = dp[i-1] + (colIsMore ? m[0][i] : m[i][0]);
	}
	for (i = 1;i < more;i++){
		dp[0] = dp[0] + (colIsMore ? m[i][0] : m[0][i]);
		for (j = 1;j < less;j++){
			dp[i] = Math.min(dp[i], dp[i-1]) + (colIsMore ? m[i][j] : m[j][i]);
		}
	}
	return arr[more - 1];

비고: 제목 에 시작 점 에서 모든 점 사이 의 최소 경 로 를 인쇄 해 야 한다 면 공간 압축 방법 을 사용 할 수 없습니다.공간 이 압축 된 후 과정 중의 값 은 덮어 져 서 거 슬러 올 라 갈 수 없다.