DP H
グリッドに障害物が置かれている、右または下に移動することで左上から右下に至る経路はいくつあるか、という問題
グリッド上の点を定義域とし、その点へ至る経路の個数を値とするDP
from 動的計画法
DP_H
H:
pythondef 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]Related Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]