洛谷 p1044 dp 栈

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int i, j;
    int n;
    cin >> n;
    long long c[20][20];//c[i][j]即出栈i个，进栈j个

    for (j = 0; j <= n; j++)
        c[0][j] = 1;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
        {
            if (i == j) c[i][j] = c[i - 1][j];
            else c[i][j] = c[i - 1][j] + c[i][j - 1];
        }
    printf("%d\n", c[n][n]);
    return 0;
}


/*
分析：运用dp的思想
①：状态：c[i][j]表示有i个出栈的，有j个进栈的  
②：再找出状态边界，转移公式。
        当出栈的个数为0时，只有唯一的结果，就是逐个出栈形成的序列
        当出栈等于进栈个数的时候，就是栈为空，它的子状态必然是唯一一种，栈里只有一个数，而出栈了i-1个
        当出栈不等于进栈时，子状态有两种，其一为进栈少一个，出栈不变，另一个则是进栈不少，但出栈少一个

*/