In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east.
For Example, D(3, 3) equals 63.
Delannoy Number can be calculated by:
Delannoy number can be used to find:
- Counts the number of global alignments of two sequences of lengths m and n.
- Number of points in an m-dimensional integer lattice that are at most n steps from the origin.
- In cellular automata, the number of cells in an m-dimensional von Neumann neighborhood of radius n.
- Number of cells on a surface of an m-dimensional von Neumann neighborhood of radius n.
Input : n = 3, m = 3
Output : 63
Input : n = 4, m = 5
Output : 681
Below is the implementation of finding Delannoy Number:
C++
#include <bits/stdc++.h>
using namespace std;
int Delannoy( int n, int m)
{
if (m == 0 || n == 0)
return 1;
return Delannoy(m - 1, n) +
Delannoy(m - 1, n - 1) +
Delannoy(m, n - 1);
}
int main()
{
int n = 3, m = 4;
cout << Delannoy(n, m) << endl;
return 0;
}
|
Java
import java.util.*;
import java.lang.*;
public class GfG{
public static int Delannoy( int n, int m)
{
if (m == 0 || n == 0 )
return 1 ;
return Delannoy(m - 1 , n) +
Delannoy(m - 1 , n - 1 ) +
Delannoy(m, n - 1 );
}
public static void main(String args[]){
int n = 3 , m = 4 ;
System.out.println(Delannoy(n, m));
}
}
|
Python3
def Delannoy(n, m):
if (m = = 0 or n = = 0 ) :
return 1
return Delannoy(m - 1 , n) + Delannoy(m - 1 , n - 1 ) + Delannoy(m, n - 1 )
n = 3
m = 4 ;
print ( Delannoy(n, m) )
|
C#
using System;
public class GfG {
public static int Delannoy( int n, int m)
{
if (m == 0 || n == 0)
return 1;
return dealnnoy(m - 1, n) +
dealnnoy(m - 1, n - 1) +
dealnnoy(m, n - 1);
}
public static void Main()
{
int n = 3, m = 4;
Console.WriteLine(dealnnoy(n, m));
}
}
|
Javascript
<script>
function Delannoy(n, m)
{
if (m == 0 || n == 0)
return 1;
return Delannoy(m - 1, n) +
Delannoy(m - 1, n - 1) +
Delannoy(m, n - 1);
}
let n = 3, m = 4;
document.write(Delannoy(n, m));
</script>
|
PHP
<?php
function Delannoy( $n , $m )
{
if ( $m == 0 or $n == 0)
return 1;
return Delannoy( $m - 1, $n ) +
Delannoy( $m - 1, $n - 1) +
Delannoy( $m , $n - 1);
}
$n = 3;
$m = 4;
echo Delannoy( $n , $m );
?>
|
Below is the Dynamic Programming program to find nth Delannoy Number:
C++
#include <bits/stdc++.h>
using namespace std;
int Delannoy( int n, int m)
{
int dp[m + 1][n + 1];
for ( int i = 0; i <= m; i++)
dp[i][0] = 1;
for ( int i = 0; i <= m; i++)
dp[0][i] = 1;
for ( int i = 1; i <= m; i++)
for ( int j = 1; j <= n; j++)
dp[i][j] = dp[i - 1][j] +
dp[i - 1][j - 1] +
dp[i][j - 1];
return dp[m][n];
}
int main()
{
int n = 3, m = 4;
cout << Delannoy(n, m) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
static int Delannoy( int n, int m)
{
int dp[][]= new int [m + 1 ][n + 1 ];
for ( int i = 0 ; i <= m; i++)
dp[i][ 0 ] = 1 ;
for ( int i = 0 ; i < m; i++)
dp[ 0 ][i] = 1 ;
for ( int i = 1 ; i <= m; i++)
for ( int j = 1 ; j <= n; j++)
dp[i][j] = dp[i - 1 ][j] +
dp[i - 1 ][j - 1 ] +
dp[i][j - 1 ];
return dp[m][n];
}
public static void main(String args[])
{
int n = 3 , m = 4 ;
System.out.println(Delannoy(n, m));
}
}
|
Python3
def Delannoy (n, m):
dp = [[ 0 for x in range (n + 1 )] for x in range (m + 1 )]
for i in range (m):
dp[ 0 ][i] = 1
for i in range ( 1 , m + 1 ):
dp[i][ 0 ] = 1
for i in range ( 1 , m + 1 ):
for j in range ( 1 , n + 1 ):
dp[i][j] = dp[i - 1 ][j] + dp[i - 1 ][j - 1 ] + dp[i][j - 1 ];
return dp[m][n]
n = 3
m = 4
print (Delannoy(n, m))
|
C#
using System;
class GFG {
static int Delannoy( int n, int m)
{
int [, ] dp = new int [m + 1, n + 1];
for ( int i = 0; i <= m; i++)
dp[i, 0] = 1;
for ( int i = 0; i < m; i++)
dp[0, i] = 1;
for ( int i = 1; i <= m; i++)
for ( int j = 1; j <= n; j++)
dp[i, j] = dp[i - 1, j]
+ dp[i - 1, j - 1]
+ dp[i, j - 1];
return dp[m, n];
}
public static void Main()
{
int n = 3, m = 4;
Console.WriteLine(Delannoy(n, m));
}
}
|
Javascript
<script>
function Delannoy(n, m)
{
var dp = Array.from(Array(m+1),
() => Array(n+1));
for ( var i = 0; i <= m; i++)
dp[i][0] = 1;
for ( var i = 0; i <= m; i++)
dp[0][i] = 1;
for ( var i = 1; i <= m; i++)
for ( var j = 1; j <= n; j++)
dp[i][j] = dp[i - 1][j] +
dp[i - 1][j - 1] +
dp[i][j - 1];
return dp[m][n];
}
var n = 3, m = 4;
document.write( Delannoy(n, m));
</script>
|
PHP
<?php
function Delannoy( $n , $m )
{
$dp [ $m + 1][ $n + 1] = 0;
for ( $i = 0; $i <= $m ; $i ++)
$dp [ $i ][0] = 1;
for ( $i = 0; $i <= $m ; $i ++)
$dp [0][ $i ] = 1;
for ( $i = 1; $i <= $m ; $i ++)
for ( $j = 1; $j <= $n ; $j ++)
$dp [ $i ][ $j ] = $dp [ $i - 1][ $j ] +
$dp [ $i - 1][ $j - 1] +
$dp [ $i ][ $j - 1];
return $dp [ $m ][ $n ];
}
$n = 3; $m = 4;
echo Delannoy( $n , $m ) ;
?>
|
Time complexity: O(m*n)
space complexity: O(n*m)
Efficient approach: Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
- Create a 1D vector dp of size n+1 and initialize it with 1.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a temporary variable prev used to store the previous computations and temp to update prev after every iteration.
- After every iteration assign the value of temp to prev for further iteration.
- At last return and print the final answer stored in dp[n].
C++
#include <bits/stdc++.h>
using namespace std;
int Delannoy( int n, int m)
{
vector< int > dp(n + 1, 1);
for ( int i = 1; i <= m; i++) {
int prev = 1;
for ( int j = 1; j <= n; j++) {
int temp = dp[j];
dp[j] = prev + dp[j] + dp[j - 1];
prev = temp;
}
}
return dp[n];
}
int main()
{
int n = 3, m = 4;
cout << Delannoy(n, m) << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static int Delannoy( int n, int m)
{
int [] dp = new int [n + 1 ];
Arrays.fill(dp, 1 );
for ( int i = 1 ; i <= m; i++) {
int prev = 1 ;
for ( int j = 1 ; j <= n; j++) {
int temp = dp[j];
dp[j] = prev + dp[j] + dp[j - 1 ];
prev = temp;
}
}
return dp[n];
}
public static void main(String[] args)
{
int n = 3 , m = 4 ;
System.out.println(Delannoy(n, m));
}
}
|
Python3
def Delannoy(n, m):
dp = [ 1 ] * (n + 1 )
for i in range ( 1 , m + 1 ):
prev = 1
for j in range ( 1 , n + 1 ):
temp = dp[j]
dp[j] = prev + dp[j] + dp[j - 1 ]
prev = temp
return dp[n]
n = 3
m = 4
print (Delannoy(n, m))
|
C#
using System;
namespace DelannoyNumber
{
class Program
{
static int Delannoy( int n, int m)
{
int [] dp = new int [n + 1];
for ( int i = 0; i <= n; i++)
{
dp[i] = 1;
}
for ( int i = 1; i <= m; i++)
{
int prev = 1;
for ( int j = 1; j <= n; j++)
{
int temp = dp[j];
dp[j] = prev + dp[j] + dp[j - 1];
prev = temp;
}
}
return dp[n];
}
static void Main( string [] args)
{
int n = 3, m = 4;
Console.WriteLine(Delannoy(n, m));
}
}
}
|
Javascript
function Delannoy(n, m) {
let dp = new Array(n + 1).fill(1);
for (let i = 1; i <= m; i++) {
let prev = 1;
for (let j = 1; j <= n; j++) {
let temp = dp[j];
dp[j] = prev + dp[j] + dp[j - 1];
prev = temp;
}
}
return dp[n];
}
let n = 3, m = 4;
console.log(Delannoy(n, m));
|
Time complexity: O(m*n)
Auxiliary space: O(n)
Contact Us