동적 계획(최대 및 삼각형 경로)

/**
 *     
 *        ，            ，           ，     
 * 
 *     ，    ，     ，         ，       ，    
 */
package dp;

import java.util.Scanner;

public class Main {
	/**
	 *         7
	 *        3 8
	 *       8 1 0
	 *      2 7 4 4
	 *     4 5 2 6 5  
	 */
	static int n = 0;//  
	static int[][] t = null;
	public static void main(String[] args) {		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();//   
		t = new int[n+1][n+1];//           		
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				t[i][j] = in.nextInt();
			}
		}
		
		//      
		//    ：maxSum(i, j) = max{maxSum(i+1, j), maxSum(i+1, j+1)}+t(i, j)       ，     ，      ，                      
		//    :maxSum(n, j) = t(n, j)                 
		//        maxSum(1, 1) = ?
		//      maxSum(int i, int j)   t[i][j]            
		System.out.println(maxSum(1, 1));
		
	}
	public static int maxSum(int i, int j){
		if(i == n) return t[i][j];
		else
			return Math.max(maxSum(i+1, j), maxSum(i+1, j+1)) + t[i][j]; //       				
	}

}
//             ，      ，         
/**
 *     
 *        ，            ，           ，     
 * 
 *     ，    ，     ，         ，       ，    （  ）
 *     ：
 *         ，             ，                 ，         ，            
 *          ，      
 */
package dp;

import java.util.Scanner;

public class Main {
	/**
	 *         7
	 *        3 8
	 *       8 1 0
	 *      2 7 4 4
	 *     4 5 2 6 5  
	 */
	static int n = 0;//  
	static int[][] t = null;//           	
	static int[][] maxSum = null;//         
	public static void main(String[] args) {		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();//   
		t = new int[n+1][n+1];
		maxSum = new int[n+1][n+1];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				t[i][j] = in.nextInt();
				maxSum[i][j] = -1;//   
			}
		}
		
		//      
		//    ：maxSum(i, j) = max{maxSum(i+1, j), maxSum(i+1, j+1)}+t(i, j)       ，     ，      ，                      
		//    :maxSum(n, j) = t(n, j)                 
		//        maxSum(1, 1) = ?
		//      maxSum(int i, int j)   t[i][j]            
		System.out.println(maxSum(1, 1));
		
	}
	public static int maxSum(int i, int j){
		//   ，               ，      
		if(maxSum[i][j] != -1) return maxSum[i][j];
		if(i == n) return t[i][j];
		else{
			//       	
			maxSum[i][j] =  Math.max(maxSum(i+1, j), maxSum(i+1, j+1)) + t[i][j];
			return maxSum[i][j];
		}						
	}

}
/**
 *     
 *        ，            ，           ，     
 * 
 *     
 *       ，         ，       ，               ，   n          ，   n-1                 
 */
package dp;

import java.util.Scanner;

public class Main {
	/**
	 *         7
	 *        3 8
	 *       8 1 0
	 *      2 7 4 4
	 *     4 5 2 6 5  
	 */
	static int n = 0;//  
	static int[][] t = null;//           	
	static int[][] maxSum = null;//         
	public static void main(String[] args) {		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();//   
		t = new int[n+1][n+1];
		maxSum = new int[n+1][n+1];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				t[i][j] = in.nextInt();
				if(i ==n){
					// n            
					maxSum[i][j] = t[i][j];
				}
			}
		}
		
		//        ，           ，        ，            
		for(int i = n-1; i >= 1; i--){//  n-1       
			for(int j = 1; j <= i; j++){//   ，           
				maxSum[i][j] = Math.max(maxSum[i+1][j], maxSum[i+1][j+1]) + t[i][j];//            
			}
		}
		//    
		System.out.println(maxSum[1][1]);
		
	}

}

/**
 *     
 *        ，            ，           ，     
 * 
 *     
 *             ，                    ,               
 *        ，                      ，        ，           
 */
package dp;

import java.util.Scanner;

public class Main {
	/**
	 *         7
	 *        3 8
	 *       8 1 0
	 *      2 7 4 4
	 *     4 5 2 6 5  
	 */
	static int n = 0;//  
	static int[][] t = null;//           	
	static int[] maxSum = null;//         
	public static void main(String[] args) {		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();//   
		t = new int[n+1][n+1];
		maxSum = new int[n+1];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				t[i][j] = in.nextInt();
				if(i ==n){
					// n            
					maxSum[j] = t[i][j];
				}
			}
		}
		
		//        ，           ，                          
		for(int i = n-1; i >= 1; i--){//  n-1       
			for(int j = 1; j <= i; j++){//   ，           
				maxSum[j] = Math.max(maxSum[j], maxSum[j+1]) + t[i][j];//            
			}
		}
		//    
		System.out.println(maxSum[1]);
		
	}

}