DP H
H - Grid 1
グリッドに障害物が置かれている、右または下に移動することで左上から右下に至る経路はいくつあるか、という問題
経路数え上げ
グリッド上の点を定義域とし、その点へ至る経路の個数を値とするDP
from
動的計画法
DP_H
H:
code:python
def solve(H, W, data):
score = [
0
* (W + 1) for i in range(H + 1)]
score
0
1
= 1
for y in range(1, H + 1):
for x in range(1, W + 1):
if data
y - 1
x - 1
== ord("#"):
score
y
x
= 0
else:
score
y
x
= (score
y - 1
x
+ score
y
x - 1
) % MOD
return score
H
W