[알고리즘][DP][1010] 다리놓기

[알고리즘][DP][1010] 다리놓기

* 풀이

package algorithm_DP;
 
import java.util.Scanner;
 
public class q_1010 {
    static int num;
    static int n, m;
    static int[][] arr;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        while(num-->0) {
 
            n = scan.nextInt();
            m = scan.nextInt();
 
            
            arr = new int[n+1][m+1];
            //1. 선을 하나 그었을 때
            for(int i=0;i<=m;i++) arr[1][i]=i;
            //2. 두번째 선부터 점화식
            for(int i=2;i<=n;i++) {
                for(int j=i;j<=m;j++) {
                    for(int k=j;k>=i;k--) {
                        arr[i][j] += arr[i-1][k-1];
                    }
                }
            }
            System.out.println(arr[n][m]);
        }
        
    }
    
 
 
}