动态规划，高阶等差数列，杨辉三角

运用动态规划，不难推导，输入整数对(m,n)其返回值F(m,n)应该是m阶等差数列的第n项。m与n的作用完全对称，F(m,n)同样也是n阶等差数列的第m项。代码见下：

#include<iostream>
#include<vector>
using namespace std;

size_t F(size_t m, size_t n)
{
    size_t m_ = max(m,n);
    size_t n_ = min(m,n);
    vector<size_t> v(n_+1,1);
    for (size_t p = 1; p<=m_; ++p)
        for (size_t q = 1; q<=n_; ++q)
            v[q] += v[q-1];
    return v.back();
}

int main(void)
{
    size_t m,n;
    while(cin>>m>>n)
        cout<<F(m,n)<<endl;
}

而事实上，F(m,n)构成了杨辉三角，故利用杨辉三角通项公式可知:

F(m,n) = (m+n)!/m!/n!

所以，也可直接使用阶乘函数进行运算。代码见下：

#include<iostream>
using namespace std;

size_t factorial( size_t n)
{
    size_t p = 1;
    for(size_t k=1; k<=n; ++k)
        p*=k;
    return p;
}

int main(void)
{
    size_t m,n;
    while(cin>>m>>n)
        cout<< factorial(m+n)/factorial(m)/factorial(n)<<endl;
}