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.
Examples :
Input : n = 3, m = 3
Output : 63
Input : n = 4, m = 5
Output : 681
Below is the implementation of finding Delannoy Number:
C++
// CPP Program of finding nth Delannoy Number.#include <bits/stdc++.h>using namespace std;// Return the nth Delannoy Number.int Delannoy(int n, int m){ // Base case if (m == 0 || n == 0) return 1; // Recursive step. return Delannoy(m - 1, n) + Delannoy(m - 1, n - 1) + Delannoy(m, n - 1);}// Driven Programint main(){ int n = 3, m = 4; cout << Delannoy(n, m) << endl; return 0;} |
Java
// Java Program for finding nth Delannoy Number.import java.util.*;import java.lang.*;public class GfG{ // Return the nth Delannoy Number. public static int Delannoy(int n, int m) { // Base case if (m == 0 || n == 0) return 1; // Recursive step. return Delannoy(m - 1, n) + Delannoy(m - 1, n - 1) + Delannoy(m, n - 1); } // driver function public static void main(String args[]){ int n = 3, m = 4; System.out.println(Delannoy(n, m)); }}/* This code is contributed by Sagar Shukla. */ |
Python3
# Python3 Program for finding # nth Delannoy Number.# Return the nth Delannoy Number.def Delannoy(n, m): # Base case if (m == 0 or n == 0) : return 1 # Recursive step. return Delannoy(m - 1, n) + Delannoy(m - 1, n - 1) + Delannoy(m, n - 1)# Driven coden = 3m = 4;print( Delannoy(n, m) )# This code is contributed by "rishabh_jain". |
C#
// C# Program for finding nth Delannoy Number.using System;public class GfG { // Return the nth Delannoy Number. public static int Delannoy(int n, int m) { // Base case if (m == 0 || n == 0) return 1; // Recursive step. return dealnnoy(m - 1, n) + dealnnoy(m - 1, n - 1) + dealnnoy(m, n - 1); } // driver function public static void Main() { int n = 3, m = 4; Console.WriteLine(dealnnoy(n, m)); }}/* This code is contributed by vt_m. */ |
Javascript
<script>// javascript Program for finding nth Delannoy Number. // Return the nth Delannoy Number. function Delannoy(n, m) { // Base case if (m == 0 || n == 0) return 1; // Recursive step. return Delannoy(m - 1, n) + Delannoy(m - 1, n - 1) + Delannoy(m, n - 1); }// Driver code let n = 3, m = 4; document.write(Delannoy(n, m)); // This code is contributed by susmitakundugoaldanga.</script> |
PHP
<?php// PHP Program of finding nth// Delannoy Number.// Return the nth Delannoy Number.function Delannoy( $n, $m){ // Base case if ($m == 0 or $n == 0) return 1; // Recursive step. return Delannoy($m - 1, $n) + Delannoy($m - 1, $n - 1) + Delannoy($m, $n - 1);} // Driver Code $n = 3; $m = 4; echo Delannoy($n, $m);// This code is contributed by anuj_67.?> |
Output
129
Below is the Dynamic Programming program to find nth Delannoy Number:
C++
// CPP Program of finding nth Delannoy Number.#include <bits/stdc++.h>using namespace std;// Return the nth Delannoy Number.int Delannoy(int n, int m){ int dp[m + 1][n + 1]; // Base cases 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];}// Driven Programint main(){ int n = 3, m = 4; cout << Delannoy(n, m) << endl; return 0;} |
Java
// Java Program of finding nth Delannoy Number.import java.io.*;class GFG { // Return the nth Delannoy Number. static int Delannoy(int n, int m) { int dp[][]=new int[m + 1][n + 1]; // Base cases 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]; } // Driven Program public static void main(String args[]) { int n = 3, m = 4; System.out.println(Delannoy(n, m)); }}// This code is contributed by Nikita Tiwari. |
Python3
# Python3 Program for finding nth# Delannoy Number.# Return the nth Delannoy Number.def Delannoy (n, m): dp = [[0 for x in range(n+1)] for x in range(m+1)] # Base cases 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]# Driven coden = 3m = 4print(Delannoy(n, m))# This code is contributed by "rishabh_jain". |
C#
// C# Program of finding nth Delannoy Number.using System;class GFG { // Return the nth Delannoy Number. static int Delannoy(int n, int m) { int[, ] dp = new int[m + 1, n + 1]; // Base cases 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]; } // Driven Program public static void Main() { int n = 3, m = 4; Console.WriteLine(Delannoy(n, m)); }}// This code is contributed by vt_m. |
Javascript
<script>// Javascript Program of finding // nth Delannoy Number.// Return the nth Delannoy Number.function Delannoy(n, m){ var dp = Array.from(Array(m+1), () => Array(n+1)); // Base cases 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];}// Driven Programvar n = 3, m = 4;document.write( Delannoy(n, m));</script> |
PHP
<?php// PHP Program of finding// nth Delannoy Number.// Return the nth Delannoy Number.function Delannoy($n, $m){ $dp[$m + 1][$n + 1] = 0; // Base cases 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];}// Driven Code$n = 3; $m = 4;echo Delannoy($n, $m) ;// This code is contributed by SanjuTomar ?> |
Output
129
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.
Implementation steps:
- 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].
Implementation:
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Return the nth Delannoy Number.int Delannoy(int n, int m){ // initialize dp vector<int> dp(n + 1, 1); // iterate over subproblems for (int i = 1; i <= m; i++) { // to keep track of previous element int prev = 1; for (int j = 1; j <= n; j++) { int temp = dp[j]; dp[j] = prev + dp[j] + dp[j - 1]; // assigning value to iterate further prev = temp; } } // return answer return dp[n];}// Driven Programint 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) { // initialize dp int[] dp = new int[n + 1]; Arrays.fill(dp, 1); // iterate over subproblems for (int i = 1; i <= m; i++) { // to keep track of previous element int prev = 1; for (int j = 1; j <= n; j++) { int temp = dp[j]; dp[j] = prev + dp[j] + dp[j - 1]; // assigning value to iterate further prev = temp; } } // return answer return dp[n]; } public static void main(String[] args) { int n = 3, m = 4; System.out.println(Delannoy(n, m)); }} |
Python3
# Python code for above approach# Return the nth Delannoy Number.def Delannoy(n, m): # initialize dp dp = [1] * (n+1) # iterate over subproblems for i in range(1, m+1): # to keep track of previous element prev = 1 for j in range(1, n+1): temp = dp[j] dp[j] = prev + dp[j] + dp[j-1] # assigning value to iterate further prev = temp # return answer return dp[n]# Driven Programn = 3m = 4print(Delannoy(n, m)) |
C#
using System;namespace DelannoyNumber{ class Program { // Return the nth Delannoy Number. static int Delannoy(int n, int m) { // Initialize dp int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) { dp[i] = 1; } // Iterate over subproblems for (int i = 1; i <= m; i++) { // To keep track of the previous element int prev = 1; for (int j = 1; j <= n; j++) { int temp = dp[j]; dp[j] = prev + dp[j] + dp[j - 1]; // Assigning value to iterate further prev = temp; } } // Return answer return dp[n]; } // Driven Program static void Main(string[] args) { int n = 3, m = 4; Console.WriteLine(Delannoy(n, m)); } }} |
Javascript
// Javascript code addition // Return the nth Delannoy Number.function Delannoy(n, m) { // initialize dp let dp = new Array(n + 1).fill(1); // iterate over subproblems for (let i = 1; i <= m; i++) { // to keep track of previous element let prev = 1; for (let j = 1; j <= n; j++) { let temp = dp[j]; dp[j] = prev + dp[j] + dp[j - 1]; // assigning value to iterate further prev = temp; } } // return answer return dp[n];}// Driven Programlet n = 3, m = 4;console.log(Delannoy(n, m));// The code is contributed by Anjali goel. |
Output
129
Time complexity: O(m*n)
Auxiliary space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!