이항계수라하면 고등학교 때 잠깐 나타나고 말 것인줄 알았거늘..... 여기서 또 마주치다니 우리에게 너무나도 익숙한 이 이항계수 nCk 어쩌구 저쩌구가 동적 계획법과 어떤 관련이 있다는건지 알아보자..^^ 이항계수란? 이항계수는 n개의 원소중에서 k개를 순서에 상관없이 뽑았을 때 조합의 가짓수이다. 파스칼의 삼각형을 이용한 이항계수의 성질은 다음과 같다. nCk = n-1Ck-1 + n-1Ck 위 식과 그림을 보면 알 수 있듯, 파스칼 삼각형에서 n-1번째 줄 k-1번째 수와 n-1번째 줄 k번째 수를 합한 값이 n번째 줄 k번째 수의 값이 된다. 즉, 이전 항들의 수의 합이 다음 항의 수가 된다. 이는 전체 문제의 부분들이 서로 상관관계가 있다는 것이고, 따라서 이항계수는 dynamic programm..