1010 다리놓기

#include <stdio.h>
#include <string.h>
 
using namespace std;
 
int dp[35][35] = { 0 };
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        for (int j = 1; j <= m; j++) {
            dp[1][j] = j;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 1;
        }
 
        for (int i = 2; i <= n; i++) {
            for (int j = i+1; j <= m; j++) {
                int sum = 0;
                for (int k = 1; k < j; k++) {
                    sum += dp[i-1][k];
                }
                dp[i][j] = sum;
            }
        }
 
        printf("%d\n", dp[n][m]);
 
        for (int i = 1; i <= n; i++) {
            memset(dp[i], 0, sizeof(int) * 34);
        }
    }
}