자연수 분할, Number Partition

static int Number_Partition (int N)
{
    int[] dp = new int[N+1];
    dp[0] = 1;

    for (int c=1; c<=N; c++)
    {
        for (int i=c; i<=N; i++)
            dp[i] += dp[i-c];
    }

    return dp[N];
}

 

자연수 N을 순서 상관없이 분할하는 모든 경우의수

 

 

 

========================================================================================================================================================================================

 

static int Number_Partition_Generic (int N, int K)
{
    int[][] dp = new int[N+1][K+1];
    dp[0][0] = 1;

    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=K; j++)
        {
            int value_1 = dp[i-1][j-1];
            int value_2 = i-j > 0 ? dp[i-j][j] : 0;

            dp[i][j] = value_1 + value_2;
        }
    }

    return dp[N][K];
}