mXnグリッドのパス数

Question

mXnグリッドのパス数を見つけるには、（1,1）から始まり、（1,1）から始まって、順列を使って、下向き、右向き、 m、n）？私は、動きが下向きおよび右向きの場合には、ストレートフォワードDP解が存在し、さらにP &C解（すなわち、m + n-2Cn-1）があることを知っている。

Answer 1

これは、既存のソリューションDPソリューションをわずかに拡張するだけで、下向きと右向きの移動のみを可能にするパスを計算するだけです。

唯一変更が必要なのは、斜めに移動するとポイントに達する方法の数を数えることです。

私がhttp://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/から取ったコードは、それをよりよく理解するのに役立ちます。

// Returns count of possible paths to reach cell at row number m and column 
// number n from the topmost leftmost cell (cell at 1, 1) 
int numberOfPaths(int m, int n) 
{ 
    // Create a 2D table to store results of subproblems 
    int count[m][n]; 

    // Count of paths to reach any cell in first column is 1 
    for (int i = 0; i < m; i++) 
     count[i][0] = 1; 

    // Count of paths to reach any cell in first column is 1 
    for (int j = 0; j < n; j++) 
     count[0][j] = 1; 

    // Calculate count of paths for other cells in bottom-up manner using 
    // the recursive solution 
    for (int i = 1; i < m; i++) 
    { 
     for (int j = 1; j < n; j++) 

      //    Rightwards  Downwards  Diagnoally right 
      count[i][j] = count[i-1][j] + count[i][j-1] + count[i-1][j-1]; 

    } 
    return count[m-1][n-1]; 
}