メモ化再起

memorization.png

動的計画法再帰的に使ったものらしい。

問題例

flow.svg
AからBまでにたどり着くには何通りの行き方があるでしょう?
gist


同じ場所に、違う経路からたどり着いた場合、
複数の経路を数えるのが無駄だよね。
そういう無駄を
深さ優先探索を、メモ配列を使って無駄な計算の2度手間を省いたものである。

ポリシー

  • 1度計算したものは2度計算しない

1度目は普通に計算して、2度めからは特別な処理を行えば良い。

やり方

探索結果をメモできる配列を用意しておく。
その配列にメモする値は、その結果にたどり着くまでに何通りあるのか
そして、同じノード(というか同じ結果)に再び来た場合は、そのメモした値を返してあげる。そうやって2度計算することを防ぐ。

ソースコード

static final int h=5,w=4;
static int[][] dp=new int[h+1][w+1]; 
    private static int dfs(int nowh,int noww){
        //範囲を超えてしまった場合
        if(nowh>h || noww>w){return 0;}
        //ゴールについた場合
        if(nowh==h && noww==w){
            return 1;
        }
        //すでに通った道だった場合
        if(dp[nowh][noww]!=0){
            return dp[nowh][noww];
        }
       return dp[nowh][noww] = dfs(nowh+1,noww)+dfs(nowh,noww+1);
    }

メモの配列dp

このソースコードでいうと、dpという配列がメモの配列です。
この配列にdp[i][j]だったら
地点(i,j)にたどり着くまで何通りの行き方があるのか?
をメモしています。

同じノードをなくした状態遷移図

main.svg

combination

サポートサイト Wikidot.com combination