c語言問題-如何理c語言中振新中華的算法

如何理c語言中振新中華的算法

下面是這道題：

標題: 振興中華

小明參加了學校的趣味運動會，其中的一個項目是：跳格子。

地上畫著一些格子，每個格子裡寫一個字，如下所示：

從我做起振
我做起振興
做起振興中
起振興中華

比賽時，先站在左上角的寫著“從”字的格子裡，可以橫向或縱向跳到相鄰的格子裡，但不能跳到對角的格子或其它位置。一直要跳到“華”字結束。


要求跳過的路線剛好構成“從我做起振興中華”這句話。

請你幫助小明算一算他一共有多少種可能的跳躍路線呢？

我在查了算法後，發現網上的普遍算法是這樣的：
#include
#define N 4
#define M 5
int main(void) {
int a[N][M];
int i, j;
for (j = 0; j < M; j++) {
a[0][j] = 1;
}
for (i = 1; i < N; i++) {
a[i][0] = 1;
for (j = 1; j < M; j++) {
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
printf("%d", a[N-1][M-1]);
return 0;
}

我想了很長時間還是想不通為啥要用二維數組這樣解題？為啥最後的線路數就是最終一致疊加的a【4】【5】的值呢？真的很難理解這個算法思想？哪位大神能仔細解答下啊！ 跪求！

最佳回答：

這個題你現在弄懂了麼？
思路大概是這樣的。
1 1 1 1 1 除了最上面一行和最左面一列只有一種路徑，其他的位置都有多種路徑。
1 2 3 4 5 每一個數字都代表著走到該位置可能的走法種數。這個方法種數，依賴於該位置
1 3 6 10 15 左列，和上一行的種數之和。（因為只能橫著和豎著走，並且目的地在右下方）
1 4 10 20 35 所以第a[3][4]這個位置上的方法就是疊加a[3][3]，a[2][4]的方法總和。