求左上角到右下角的所有路径 Approach: Recursion- Earlier we have seen “Print All Paths from Top left to bottom right in Two Dimensional Array“. Current problem is the subset of that problem. Here we will just count the number of paths, will not print them.
From every cell you will have two options to make a move, either to go right OR down. Base case will be check if you have reached to either last row OR last column then there is only one way to reach the last cell is to travel through that row or column. x
Recursion is the key here. Take the rows count and column counts say rowCount and colCount respectively Take currentRow =0 and currentColumn =0 and path =”” Call printAll(currentRow, currentcolumn,path) Add array[0][0] to the path. Call recursively printAll(currentRow+1, currentcolumn,path) Call recursively printAll(currentRow, currentcolumn+1,path) 每到一个新的pixel再次向下且向右递归
Base Case 1: when currentRow = rowCount-1(because array index starts with 0) , print the rest of the columns, return Base Case 2: when currentcolumn = colCount-1(because array index starts with 0) , print the rest of the rows, return Recursive Code: 从（0,0）开始：
public int count(int [][] arrA, int row, int col){ //base case //check if last row OR column is reached since after that only one path //is possible to reach to the bottom right corner. if(row==arrA.length-1 || col==arrA.length-1){ return 1; } return count(arrA, row+1, col) + count(arrA, row, col+1); }从（m,n）开始：
class Solution{ long numberOfPaths(int m, int n) { // Code Here if(m == 1 || n == 1) { return 1; } return numberOfPaths( m-1, n) + numberOfPaths(m, n -1); } }Reference: 1.https://algorithms.tutorialhorizon.com/print-all-paths-from-top-left-to-bottom-right-in-two-dimensional-array/ 2.https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/ 3.https://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
