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

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

## 本文概述

``````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)``````

## 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
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
# 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
return numberOfPaths( \$m - 1, \$n ) +
numberOfPaths( \$m , \$n - 1);
}

// Driver Code
echo numberOfPaths(3, 3);

// This code is contributed by akt_mit
?>``````

``6``

.

)的动态编程问题。像其他典型的

, 通过使用上述递归公式以自底向上的方式构造一个临时数组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] = 1;

// Count of paths to reach any cell in first row is 1
for ( int j = 0; j < n; j++)
count[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 ] = 1;

// Count of paths to reach any cell
// in first column is 1
for ( \$j = 0; \$j < \$n ; \$j ++)
\$count [ \$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``

DP解决方案的空间优化。

## 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 = 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

## 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 = 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  = 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``

(使用组合运算法则)在这种方法中, 我们必须计算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`` 