Editorial for Atcoder Educational DP Contest H - Grid 1
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Độ 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; }
Comments