瞬間移動

Accepts: 1018 Submissions: 3620
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description
有一個無限大的矩形，初始時你在左上角（即第一行第一列），每次你都可以選擇一個右下方格子，并瞬移過去（如從下圖中的紅色格子能直接瞬移到藍色格子），求到第n行第m列的格子有幾種方案，答案對1000000007取模。

Input
多組測試數據。
兩個整數n,m(2≤n,m≤100000)

Output
一個整數表示答案

Sample Input
4 5

Sample Output
10

我的代碼

一、遞歸法

思路：到達第n行第m列的格子的方案數=到達第i行(1-n)第j(1-m)列的格子的方案數的總和+1（直接從1,1移動到目標處）。用遞歸實現。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>using namespace std;long fun(int a, int b) {long result = 1;if (a == 2 || b == 2) {return result;}ielse {for (int i = a - 1;i > 1;i--) {for (int j = b - 1;j > 1;j--) {result += fun(i, j);result = result % 1000000007;}}}return result;
}
int main() {int n, m;while (cin >> n >> m) {cout << fun(n, m) << endl;}return 0;
}

缺點：超時。時間復雜度高。對靠近1,1處的許多格子的路徑數進行了大量重復計算。可不可以減少這些冗余計算？

二、用二維數組存儲

思路：要計算到達第n行第m列的格子的方案數,就要分別計算到達第i(1-n)行第j(1-m)列的格子的方案數,然后對他們求和。為了避免重復計算，可以將每一個格子對應的到達它本身的方案數存起來。這樣可以大大減小冗余計算，減小時間復雜度，代價是空間消耗。

#include <iostream>using namespace std;long a[100000][100000];long result;
void sum(int b, int c) {for (int i = 0;i<b;i++) {for (int j = 0;j<c;j++) {a[b][c] += a[i][j];a[b][c] = a[b][c] % 1000000007;}}return;
}
int main() {int n, m;while (cin >> n >> m) {result = 1;for (int i = 2;i < n;i++) {for (int j = 2;j < m;j++) {if (i == 2 || j == 2)a[i - 2][j - 2] = 1;else {sum(i - 2, j - 2);}}}cout << a[n - 2][m - 2] << endl;}return 0;
}

缺點：空間復雜度太大，n和m最大是100000，所以這種方法所需要的數組長度最大竟然可達10的10次方，即80GB！

改進思路：在方法二的基礎上，先考慮正方形這一特殊情況，用大小為100000的數組存儲到達第n行第n列的格子的方案數。不失一般性，假設m>n,則第n行第m列的格子的方案數比第n行第n列的格子多出了“從第（m-n）列到達目的”的方案數。這第（m-n）列可能是多列，行序號是2-(n-1)。不過這些處于正方形之外的格子和那些不在右斜對角線上的格子一樣，又涉及重復計算，導致時間復雜度升高。所以這算是方法一和方法二的一種平衡。但時間復雜度能降多少，還有待實驗驗證。