조합 문제. 중복조합

문제

https://www.acmicpc.net/problem/2225

설명

• 조합자체는 파스칼의 삼각형으로 알 수 있다 .
• 파스칼 삼각형과 조합에 대해 잘 설명해준 블로그를 참고하였다 (https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients)

• 첫번재를 0으로 생각하면 0 1 2 위에서 3번째 왼쪽에서 2번째 따라서 3C2이다.
• 또한 nCk = n-1Ck-1 + n -1Ck로 구할 수 있다

• 중복조합의 공식은 nHk이다 nHk는 n+k - 1C k 이다

• 이런 dp문제에서 기본 베이스값은 C(n, 0) = 1, C(n, n) = 1
• C(i, 0) == C(i, i) = 1 for all i

소스

#include <bits/stdc++.h>

using  namespace std;

int dp[300][300];  //현재 n개중에서 k개의 바구니 
int n, k;

//C(n,k) = C(n-1,k-1) + C(n-1,k)
int solve(int n, int k) {

   if (n == 0 && k == 0) return 0;

   if (dp[n][k] != -1) {
      return dp[n][k];
   }

   dp[n][k] = solve(n - 1, k - 1) + solve(n - 1, k);

   return dp[n][k];
}
int main() {

   cin >> n >> k;

   memset(dp, -1, sizeof(dp));

   //base 값 C(i,0) = C(i,i) = 1 for all i, C(n,0) = 1, C(n,n) = 1
   for (int i = 0; i < n; i++)
   {
      dp[i][0] = 1;
      dp[i][i] = 1;
   }

   cout << solve(n, k);
   return 0;
}