计算从mXn矩阵的左上到右下的所有可能路径

2021年3月12日13:31:44 发表评论 844 次浏览

本文概述

问题是要计算从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 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)
     {
         // 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

C#

// 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)
     {
         // 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 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 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

C#

// 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)。

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

C#

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#

// 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.

输出如下：

6

本文作者：哈里普拉萨德(NG)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: