파스칼의 삼각형 공식

C(n,k)=C(n−1,k−1)+C(n−1,k) (n>=k)
C(4,2)=C(3,1)+C(3,2)

C(3,1)=C(2,0)+C(2,1)C(3, 1) = C(2, 0) + C(2, 1)

C(3,1)=C(2,0)+C(2,1)

C(3,2)=C(2,1)+C(2,2)C(3, 2) = C(2, 1) + C(2, 2)

C(3,2)=C(2,1)+C(2,2)

동적 계획법(DP)을 사용한 해결

[백준 1010]

function run(inputs: string[]) {
  const result = [];

  for (const input of inputs) {
    const [a, b] = input.split(' ').map(Number);
    console.log(a, b);

    const dp: number[][] = Array.from({ length: b + 1 }, () =>
      Array(a + 1).fill(-1),
    );

    function combination(num1: number, num2: number): number {
      if (num2 === 0 || num1 === num2) return 1;
      if (dp[num1][num2] !== -1) return dp[num1][num2];

      dp[num1][num2] =
        combination(num1 - 1, num2 - 1) + combination(num1 - 1, num2);
      return dp[num1][num2];
    }

    const comb = combination(b, a);
    result.push(comb);
  }

  return result.join('\\n');
}