计算从mXn矩阵的左上到右下的所有可能路径 _最大求和路径

本文概述问题是要计算从mXn矩阵的左上角到右下角的所有可能路径, 其中在每个单元格中, 你只能向右或向下移动
例子：

Input :m = 2, n = 2; Output : 2 There are two paths (0, 0) -> (0, 1) -> (1, 1) (0, 0) -> (1, 0) -> (1, 1)Input :m = 2, n = 3; Output : 3 There are three paths (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) (0, 0) -> (1, 0) -> (1, 1) -> (1, 2)

推荐：请在"实践首先, 在继续解决方案之前。
我们已经讨论了打印所有可能路径的解决方案, 计算所有路径更加容易。令NumberOfPaths(m, n)为到达矩阵中行号m和列号n的路径数, NumberOfPaths(m, n)可以递归编写如下。
C ++

// A C++program to count all possible paths // from top left to bottom right#include < iostream> using namespace std; // 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) { // If either given row number is first or given column // number is first if (m == 1 || n == 1) return 1; // If diagonal movements are allowed then the last // addition is required. return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1); // + numberOfPaths(m-1, n-1); }int main() { cout < < numberOfPaths(3, 3); return 0; }

Java

// A Java program to count all possible paths // from top left to bottom rightclass GFG {// 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) static int numberOfPaths( int m, int n) { // If either given row number is first or // given column number is first if (m == 1 || n == 1 ) return 1 ; // If diagonal movements are allowed then // the last addition is required. return numberOfPaths(m - 1 , n) + numberOfPaths(m, n - 1 ); // + numberOfPaths(m-1, n-1); }public static void main(String args[]) { System.out.println(numberOfPaths( 3 , 3 )); } }// This code is contributed by Sumit Ghosh

python

# Python program to count all possible paths # from top left to bottom right# function to return count of possible paths # to reach cell at row number m and column # number n from the topmost leftmost # cell (cell at 1, 1) def numberOfPaths(m, n): # If either given row number is first # or given column number is first if (m = = 1 or n = = 1 ): return 1# If diagonal movements are allowed # then the last addition # is required. return numberOfPaths(m - 1 , n) + numberOfPaths(m, n - 1 )# Driver program to test above function m = 3 n = 3 print (numberOfPaths(m, n))# This code is contributed by Aditi Sharma

// A C# program to count all possible paths // from top left to bottom rightusing System; public class GFG { // 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) static int numberOfPaths( int m, int n) { // If either given row number is first or // given column number is first if (m == 1 || n == 1) return 1; // If diagonal movements are allowed then // the last addition is required. return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1); // + numberOfPaths(m-1, n-1); }static public void Main() { Console.WriteLine(numberOfPaths(3, 3)); } }// This code is contributed by ajit

的PHP

< ?php// 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) function numberOfPaths( $m , $n ) {// If either given row number // is first or given column // number is first if ( $m == 1 || $n == 1) return 1; // If diagonal movements // are allowed then the last // addition is required. return numberOfPaths( $m - 1, $n ) + numberOfPaths( $m , $n - 1); }// Driver Code echo numberOfPaths(3, 3); // This code is contributed by akt_mit ?>

输出如下：

6

上述递归解的时间复杂度是指数的。有许多重叠的子问题。我们可以为numberOfPaths(3, 3)绘制一个递归树, 并看到许多重叠的子问题。递归树将类似于
最长公共子序列问题的递归树
.
因此, 此问题具有两个属性(请参阅
这个
和
这个
)的动态编程问题。像其他典型的
动态编程(DP)问题
, 通过使用上述递归公式以自底向上的方式构造一个临时数组count [] [], 可以避免相同子问题的重新计算。
C ++

// A C++ program to count all possible paths // from top left to bottom right #include < iostream> using namespace std; // Returns count of possible paths to reach cell at // row number m and columnnumber 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 row 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++)// By uncommenting the last part the code calculates the total // possible paths if the diagonal Movements are allowed count[i][j] = count[i - 1][j] + count[i][j - 1]; //+ count[i-1][j-1]; } return count[m - 1][n - 1]; }// Driver program to test above functions int main() { cout < < numberOfPaths(3, 3); return 0; }

Java

// A Java program to count all possible paths // from top left to bottom right class GFG { // 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) static int numberOfPaths( int m, int n) { // Create a 2D table to store results // of subproblems int count[][] = new int [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++)// By uncommenting the last part the // code calculates the total possible paths // if the diagonal Movements are allowed count[i][j] = count[i - 1 ][j] + count[i][j - 1 ]; //+ count[i-1][j-1]; } return count[m - 1 ][n - 1 ]; }// Driver program to test above function public static void main(String args[]) { System.out.println(numberOfPaths( 3 , 3 )); } }// This code is contributed by Sumit Ghosh

python

# Python program to count all possible paths # from top left to bottom right# 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) def numberOfPaths(m, n): # Create a 2D table to store # results of subproblems count = [[ 0 for x in range (m)] for y in range (n)]# Count of paths to reach any # cell in first column is 1 for i in range (m): count[i][ 0 ] = 1 ; # Count of paths to reach any # cell in first column is 1 for j in range (n): count[ 0 ][j] = 1 ; # Calculate count of paths for other # cells in bottom-up # manner using the recursive solution for i in range ( 1 , m): for j in range ( 1 , n): count[i][j] = count[i - 1 ][j] + count[i][j - 1 ] return count[m - 1 ][n - 1 ]# Driver program to test above function m = 3 n = 3 print ( numberOfPaths(m, n))# This code is contributed by Aditi Sharma

// A C#program to count all possible paths // from top left to bottom right using System; public class GFG {// 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) static int numberOfPaths( int m, int n) { // Create a 2D table to store results // of subproblems int [, ] count = new int [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++)// By uncommenting the last part the // code calculates the total possible paths // if the diagonal Movements are allowed count[i, j] = count[i - 1, j] + count[i, j - 1]; //+ count[i-1][j-1]; } return count[m - 1, n - 1]; }// Driver program to test above function static public void Main() { Console.WriteLine(numberOfPaths(3, 3)); } }// This code is contributed by akt_mit

的PHP

< ?php // A PHP program to count all possible // paths from top left to bottom right// 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) function numberOfPaths( $m , $n ) { // Create a 2D table to store // results of subproblems $count = array (); // Count of paths to reach any cell // in first column is 1 for ( $i = 0; $i < $m ; $i ++) $count [ $i ][0] = 1; // Count of paths to reach any cell // in first column is 1 for ( $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 ( $i = 1; $i < $m ; $i ++) { for ( $j = 1; $j < $n ; $j ++)// By uncommenting the last part the // code calculated the total possible // paths if the diagonal Movements are allowed $count [ $i ][ $j ] = $count [ $i - 1][ $j ] + $count [ $i ][ $j - 1]; //+ count[i-1][j-1]; } return $count [ $m - 1][ $n - 1]; }// Driver Code echo numberOfPaths(3, 3); // This code is contributed // by Mukul Singh ?>

输出如下：

6

上述动态编程解决方案的时间复杂度为O(mn)。
上述解决方案的空间复杂度为O(mn)。
【计算从mXn矩阵的左上到右下的所有可能路径】DP解决方案的空间优化。
上面的解决方案更直观, 但我们也可以将空间减少O(n); 其中n是列大小。
C ++

#include < bits/stdc++.h> using namespace std; // 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 1D array to store results of subproblems int dp[n] = { 1 }; dp[0] = 1; for ( int i = 0; i < m; i++) { for ( int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } }return dp[n - 1]; }// Driver code int main() { cout < < numberOfPaths(3, 3); }// This code is contributed by mohit kumar 29

Java

class GFG { // 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) static int numberOfPaths( int m, int n) { // Create a 1D array to store results of subproblems int [] dp = new int [n]; dp[ 0 ] = 1 ; for ( int i = 0 ; i < m; i++) { for ( int j = 1 ; j < n; j++) { dp[j] += dp[j - 1 ]; } }return dp[n - 1 ]; }// Driver program to test above function public static void main(String args[]) { System.out.println(numberOfPaths( 3 , 3 )); } }

Python3

# 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) def numberOfPaths(p, q):# Create a 1D array to store # results of subproblems dp = [ 1 for i in range (q)] for i in range (p - 1 ): for j in range ( 1 , q): dp[j] + = dp[j - 1 ] return dp[q - 1 ]# Driver Code print (numberOfPaths( 3 , 3 ))# This code is contributed # by Ankit Yadav

using System; class GFG { // 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) static int numberOfPaths( int m, int n) { // Create a 1D array to store // results of subproblems int [] dp = new int [n]; dp[0] = 1; for ( int i = 0; i < m; i++) { for ( int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } }return dp[n - 1]; }// Driver Code public static void Main() { Console.Write(numberOfPaths(3, 3)); } }// This code is contributed // by ChitraNayal

的PHP

< ?php // 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) function numberOfPaths( $m , $n ) { // Create a 1D array to store // results of subproblems $dp = array (); $dp [0] = 1; for ( $i = 0; $i < $m ; $i ++) { for ( $j = 1; $j < $n ; $j ++) { $dp [ $j ] += $dp [ $j - 1]; } }return $dp [ $n - 1]; }// Driver Code echo numberOfPaths(3, 3); // This code is contributed // by Akanksha Rai ?>

输出如下：

6

该代码由维维克·辛格(Vivek Singh)
注意, 也可以使用公式(m-1 + n-1)！/(m-1)！(n-1)！计算计数。
另一种方法：
(使用组合运算法则)在这种方法中, 我们必须计算m + n-2 C n-1, 这将是(m + n-2)！ /(n-1)！ (m-1)！
C ++

// A C++ program to count all possible paths from // top left to top bottom using combinatorics#include < iostream> using namespace std; int numberOfPaths( int m, int n) { // We have to calculate m+n-2 C n-1 here // which will be (m+n-2)! / (n-1)! (m-1)! int path = 1; for ( int i = n; i < (m + n - 1); i++) { path *= i; path /= (i - n + 1); } return path; }// Driver code int main() { cout < < numberOfPaths(3, 3); return 0; }// This code is suggested by Kartik Sapra

Java

// Java program to count all possible paths from // top left to top bottom using combinatorics class GFG {static int numberOfPaths( int m, int n) { // We have to calculate m+n-2 C n-1 here // which will be (m+n-2)! / (n-1)! (m-1)! int path = 1 ; for ( int i = n; i < (m + n - 1 ); i++) { path *= i; path /= (i - n + 1 ); } return path; }// Driver code public static void main(String[] args) { System.out.println(numberOfPaths( 3 , 3 )); } }// This code is contributed by Code_Mech.

Python3

# Python3 program to count all possible # paths from top left to top bottom # using combinatorics def numberOfPaths(m, n) :# We have to calculate m + n-2 C n-1 here # which will be (m + n-2)! / (n-1)! (m-1)! path = 1; for i in range (n, (m + n - 1 )): path * = i; path / / = (i - n + 1 ); return path; # Driver code print (numberOfPaths( 3 , 3 )); # This code is contributed # by Akanksha Rai

// C# program to count all possible paths from // top left to top bottom using combinatorics using System; class GFG {static int numberOfPaths( int m, int n) { // We have to calculate m+n-2 C n-1 here // which will be (m+n-2)! / (n-1)! (m-1)! int path = 1; for ( int i = n; i < (m + n - 1); i++) { path *= i; path /= (i - n + 1); } return path; }// Driver code public static void Main() { Console.WriteLine(numberOfPaths(3, 3)); } }// This code is contributed by Code_Mech.

的PHP

< ?php// PHP program to count all possible paths from // top left to top bottom using combinatorics function numberOfPaths( $m , $n ) { // We have to calculate m+n-2 C n-1 here // which will be (m+n-2)! / (n-1)! (m-1)! $path = 1; for ( $i = $n ; $i < ( $m + $n - 1); $i ++) { $path *= $i ; $path /= ( $i - $n + 1); } return $path ; }// Driver code { echo (numberOfPaths(3, 3)); }// This code is contributed by Code_Mech.

输出如下：