動的計画法について読んでいます。上手になるには練習と直感が必要だと読みましたが、このアドバイスは一般的なように思えます。
私にとって最も難しいのは、再帰式を理解することです。ソリューションで使用されている数式が直感的に理解できない場合があります。
たとえば、次の問題を読みました。
2 つの文字列 S と T があります。S が T に出現する回数を見つけるアルゴリズムを与えてください。S のすべての文字が T で連続して出現することは必須ではありません。
解決策は、次の再帰式に基づいていますが、私にとってはまったく直感的ではありません。
M(i, j) は、S の i 文字が T の j 文字に出現する回数を表すと仮定します。基本ケース:
i) j = 0 の場合は 0
ii) i = 0 の場合は 1
DPを介して問題を解決するための適切な再帰式を定義/見つけるのに役立つ、問題のある種の「分析」があるのではないかと思っていましたか?