問題描述：
有下面一個這樣的圖形，我們從原點 (0,0) 出發，每次移動只能往上、往右、往右上三種方向其中一種前進。我們可以人工的方式算出走到 (1,1) 有 2 種走法、 (2,2) 有 6 種走法。
現在要你寫一個程式，計算從 (0,0) 走到 (n,n)，(1 <= n <= 15) ，共有幾種走法。

輸入說明：
第一行為一個正整數 m 表示共有 m 組測試資料，其後有 m 行，每行有一個介於 1 到 15 之間的正整數 。

輸出說明：
每組測試資料結果 輸出於一行 。

图形是：（好像不能贴图吧？压缩了再上传的，麻烦大神看看！）


範例：

Sample Input:          Sample Output:
 
2                         2

1                         6

2
 



 
 

算法才是编程的精华之所在啊。。。
不懂之好帮顶了

真变态呀，一张图片不直接贴出来，却先贴到M$ office中，真是脱裤子放屁，你自己不觉得麻烦，看得人也会觉得麻烦呀

“只能往上、往右、往右上”
--- 可以得出，到(a,b)的走法数 = 到(a-1,b)的走法数 + 到(a-1,b-1)的走法数 + 到(a,b-1)的走法数
因此，递归算法就是

unsigned f( int a, int b )
{
    if( a <  b )
        return 0;

    if( b == 0 )
        return 1;

    return f(a-1,b) + f(a-1,b-1) + f(a,b-1);
}

#include <iostream>

int main()
{
    std::cout << f(2,2) << std::endl;

    return 0;
}

多么简单呀

但一般而言，只有SB才用递归算法（只是一般而言，不代表全部），因此将递归算法反过来，一层层的累加

typedef unsigned int U32T;
U32T f( unsigned n )
{
    U32T* p_ = new U32T[n+2];
    p_[0] = 0;
    U32T* p = p_ + 1;
    for( U32T i=0; i<n+1; ++i )
        p[i] = 1;

    for( U32T i=1; i<=n; ++i )
    {
        for( U32T j=0; j<=n-i; ++j )
        {
            p[j] = p[j-1] + p[j] + p[j+1];
        }
    }

    U32T r = p[0];
    delete[] p_;
    return r;
}

#include <iostream>

int main()
{
    for( unsigned i=1; i<=15; ++i )
        std::cout << i << " = " << f(i) << std::endl;

    return 0;
}

输出为
1 = 2
2 = 6
3 = 22
4 = 90
5 = 394
6 = 1806
7 = 8558
8 = 41586
9 = 206098
10 = 1037718
11 = 5293446
12 = 27297738
13 = 142078746
14 = 745387038
15 = 3937603038

顶版主 学习一下