Độ phức tạp thời gian: ~O(N^2)~

Gọi ~dp[x][y]~ là số lượng đường đi từ ô ~(1,1)~ đến ô ~(x,y)~.

Ô ~(x,y)~ bất kì có thể được đi đến từ ô ~(x,y-1)~ hoặc ô ~(x-1,y)~, vì vậy, ta có thể xây dựng công thức:

~dp[x][y] = dp[x-1][y] + dp[x][y-1]~

Ta có, ~dp[1][1] = 1~ vì đường đi từ ô ~(1,1)~ tới ô ~(1,1)~ chỉ có duy nhất một cách.

Như vậy, chúng ta có thể áp dụng công thức này để tính ~dp[H][W]~

Hướng dẫn cài đặt:

#include<bits/stdc++.h>

using namespace std;

bool ok[1005][1005] = {};
long long dp[1005][1005] = {};
int h,w;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout .tie(0);



    cin >> h >> w;


    for(int i = 1; i <= h; ++i) {
        string s;
        cin >> s;
        s = ' ' + s;
        for(int j = 1; j <= w; ++j) {
            if(s[j] == '.') ok[i][j] = true;
            else ok[i][j] = false;
        }
    }

    dp[1][1] = 1;
    for(int i = 1; i <= h; ++i) {
        for(int j = 1; j <= w; ++j) {
            if(!ok[i][j]) dp[i][j] = 0;
            else {
                if(i > 1) dp[i][j] += dp[i - 1][j];
                if(j > 1) dp[i][j] += dp[i][j - 1];
                dp[i][j] %= 1000000007;
            }
        }
    }

    cout << dp[h][w] << "\n";


    return 0;
}