深さ優先探索，動的計画法，メモ化再帰

ITmediaにて，chokudai(高橋直大)さん連載の「最強最速アルゴリズマー養成講座」の最新記事が公開されました．

最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html

というわけで，格子の問題を，解説を元にサクッと組んでみました．

public class Main{
 private int w, h;
 private int[][] memo;
 
 private int recursive1(int[][] grid, int x, int y){
  if(y==0&&x==w-1){
   return 1;
  }
  else if(y<0||x>=w||grid[y][x]==1){
   return 0;
  }
  else {
   return recursive1(grid, x+1, y)+recursive1(grid, x, y-1);
  }
 }
 
 // 単純な深さ優先探索(DFS) O(2^(h+m))
 private int count1(int[][] grid){
  w=grid[0].length;
  h=grid.length;
  return recursive1(grid,0,h-1);
 }
 
 // 動的計画法(DP) O(h*w)
 private int count2(int[][] grid){
  w=grid[0].length;
  h=grid.length;
  int[] a=new int[w];
  
  for(int i=0;i<w&&grid[h-1][i]==0;i++){
   a[i]=1;
  }
  
  for(int j=h-2;j>=0;j--){
   for(int i=1;i<w;i++){
    if(grid[j][i]==1)
     a[i]=0;
    else
     a[i]+=a[i-1];
   }
  }
  return a[w-1];
 }
 
 private int recursive3(int[][] grid, int x, int y){
  if(y==0&&x==w-1){
   return 1;
  }
  else if(y<0||x>=w||grid[y][x]==1){
   return 0;
  }
  else {
   if(memo[y][x]!=0)
    return memo[y][x];
   else
    return memo[y][x]=recursive3(grid, x+1, y)+recursive3(grid, x, y-1);
  }
 }
 
 // メモ化再帰
 private int count3(int[][] grid){
  w=grid[0].length;
  h=grid.length;
  memo=new int[h][w];
  return recursive3(grid,0,h-1);
 }
 
 public static void main(String[] args){
  // 0:通過可能
  // 1:通過不可能
  int[][] grid=new int[][]
  {
   {0,0,0,0,0,0},
   {0,1,0,0,0,0},
   {0,0,0,0,1,0},
   {0,0,1,0,0,0},
   {0,0,0,0,0,0},
  };
  System.out.println("1:"+new Main().count1(grid));
  System.out.println("2:"+new Main().count2(grid));
  System.out.println("3:"+new Main().count3(grid));
 }
}

深さ優先探索，動的計画法，メモ化再帰の3つです．意外なほど簡単に組めたので驚き．

「最強最速アルゴリズマー養成講座」の記事一覧は下記から．

「最強最速アルゴリズマー養成講座」最新記事一覧 - ITmedia Keywords
http://www.itmedia.co.jp/keywords/algorithmer.html