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

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

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

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

view plainprint?

1. public class Main{  
2.  private int w, h;  
3.  private int[][] memo;  
4.    
5.  private int recursive1(int[][] grid, int x, int y){  
6.   if(y==0&&x==w-1){  
7.    return 1;  
8.   }  
9.   else if(y<0||x>=w||grid[y][x]==1){  
10.    return 0;  
11.   }  
12.   else {  
13.    return recursive1(grid, x+1, y)+recursive1(grid, x, y-1);  
14.   }  
15.  }  
16.    
17.  // 単純な深さ優先探索(DFS) O(2^(h+m))  
18.  private int count1(int[][] grid){  
19.   w=grid[0].length;  
20.   h=grid.length;  
21.   return recursive1(grid,0,h-1);  
22.  }  
23.    
24.  // 動的計画法(DP) O(h*w)  
25.  private int count2(int[][] grid){  
26.   w=grid[0].length;  
27.   h=grid.length;  
28.   int[] a=new int[w];  
29.     
30.   for(int i=0;i<w&&grid[h-1][i]==0;i++){  
31.    a[i]=1;  
32.   }  
33.     
34.   for(int j=h-2;j>=0;j--){  
35.    for(int i=1;i<w;i++){  
36.     if(grid[j][i]==1)  
37.      a[i]=0;  
38.     else  
39.      a[i]+=a[i-1];  
40.    }  
41.   }  
42.   return a[w-1];  
43.  }  
44.    
45.  private int recursive3(int[][] grid, int x, int y){  
46.   if(y==0&&x==w-1){  
47.    return 1;  
48.   }  
49.   else if(y<0||x>=w||grid[y][x]==1){  
50.    return 0;  
51.   }  
52.   else {  
53.    if(memo[y][x]!=0)  
54.     return memo[y][x];  
55.    else  
56.     return memo[y][x]=recursive3(grid, x+1, y)+recursive3(grid, x, y-1);  
57.   }  
58.  }  
59.    
60.  // メモ化再帰  
61.  private int count3(int[][] grid){  
62.   w=grid[0].length;  
63.   h=grid.length;  
64.   memo=new int[h][w];  
65.   return recursive3(grid,0,h-1);  
66.  }  
67.    
68.  public static void main(String[] args){  
69.   // 0:通過可能  
70.   // 1:通過不可能  
71.   int[][] grid=new int[][]  
72.   {  
73.    {0,0,0,0,0,0},  
74.    {0,1,0,0,0,0},  
75.    {0,0,0,0,1,0},  
76.    {0,0,1,0,0,0},  
77.    {0,0,0,0,0,0},  
78.   };  
79.   System.out.println("1:"+new Main().count1(grid));  
80.   System.out.println("2:"+new Main().count2(grid));  
81.   System.out.println("3:"+new Main().count3(grid));  
82.  }  
83. }  

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