동적 계획 알고리즘 의 수 탑 문제

문제 설명
수 탑 꼭대기 층 에서 출발 하여 모든 결점 은 왼쪽으로 가 거나 오른쪽으로 가 는 것 을 선택 할 수 있 으 며 탑 밑 까지 걸 어가 서 걸 어 가 는 경로 의 수치 와 최대 치 를 요구 할 수 있다.
위의 그림 에서 보 듯 이 수 탑 은 최대 경로 와 86 이 고 지나 가 는 경 로 는 탑 꼭대기 에서 탑 밑 까지 13, 8, 26, 15, 24 이다.
문제 분석
동적 계획 함수:
resultTower[i][j] = tower[i][j] + Math.max(tower[i + 1][j],tower[i + 1][j + 1]);
경계 값 resultTower [heigh - 1] [j] = tower [heigh - 1] [j];
3. 알고리즘 코드

public int dataTower(int tower[][]){
		int heigh = tower.length;//    
		int len = tower[heigh - 1].length;//      
		int [][] resultTower = new int[heigh][len];//    ，       
		int [][] path = new int[heigh][len];//          
		
		//       
		for(int i = 0; i < len; i++){
			resultTower[heigh - 1][i] = tower[heigh - 1][i];
		}
		
		//           
		for(int i = heigh - 2; i >= 0; i--){
			for(int j = 0; j <= i; j++){
				if(resultTower[i + 1][j] > resultTower[i + 1][j + 1]){
					resultTower[i][j] = tower[i][j] + resultTower[i + 1][j];
					path[i][j] = j; 
				}else{
					resultTower[i][j] = tower[i][j] + resultTower[i + 1][j + 1]; 
					path[i][j] = j + 1;
				}
			}
		}
		
		//    
		System.out.println("      " + resultTower[0][0] + "
       :");
		System.out.println(" 0   ：" + tower[0][0]);
		int j = path[0][0];
		for(int i = 1; i <= heigh - 1; i++){
			System.out.println(" " + i + "   ：" + tower[i][j]);
			j = path[i][j];
		}
		System.out.println();
		
		return resultTower[0][0];
	}

4. 전체 테스트 코드

public class Solution {
	
	public static void main(String [] args){
		int [][] tower = {{13},{11,8},{12,7,26},{6,14,15,8},{12,7,13,24,11}};
		int result = dataTower(tower);
	}
	public static int dataTower(int tower[][]){
		int heigh = tower.length;//    
		int len = tower[heigh - 1].length;//      
		int [][] resultTower = new int[heigh][len];//    ，       
		int [][] path = new int[heigh][len];//          
		
		//       
		for(int i = 0; i < len; i++){
			resultTower[heigh - 1][i] = tower[heigh - 1][i];
		}
		
		//           
		for(int i = heigh - 2; i >= 0; i--){
			for(int j = 0; j <= i; j++){
				if(resultTower[i + 1][j] > resultTower[i + 1][j + 1]){
					resultTower[i][j] = tower[i][j] + resultTower[i + 1][j];
					path[i][j] = j; 
				}else{
					resultTower[i][j] = tower[i][j] + resultTower[i + 1][j + 1]; 
					path[i][j] = j + 1;
				}
			}
		}
		
		//    
		System.out.println("      " + resultTower[0][0] + "
       :");
		System.out.println(" 0   ：" + tower[0][0]);
		int j = path[0][0];
		for(int i = 1; i <= heigh - 1; i++){
			System.out.println(" " + i + "   ：" + tower[i][j]);
			j = path[i][j];
		}
		System.out.println();
		
		return resultTower[0][0];
	}
}

운행 결과

      86
       :
 0   ：13
 1   ：8
 2   ：26
 3   ：15
 4   ：24