Consider a two dimensional array $dp$, where dp[i][j] represents the number of ways the turtle can get from cell $(1,1)$ to cell $(i,j)$. We set dp[1][1] = 1.

The turtle can reach cell $(i,j)$ either from cell (i - 1, j) or from cell (i, j - 1). Therefore, the following equality holds:

Initially, we'll zero out the $dp$ array. Special attention is paid to zeroing the first row and first column of the dp array.

• If i = 1, then dp[i - 1][j] = dp[0][j] = 0, and the dynamic programming equation simplifies to dp[1][j] = dp[1][j - 1]. This is how the first row is recalculated.

• If j = 1, the formula becomes dp[i][1] = dp[i - 1][1]. This is how the first column is recalculated.

Given that dp[1][1] = 1, we can conclude that all cells in the first row and the first column will contain the value $1$, which corresponds to the only way to reach each of these cells.

Example

Fill the $dp$ array for the grid of size 4 \times 3:

Algorithm implementation

Declare the $dp$ array.

#define MAX 31
long long dp[MAX][MAX];

Read the input data.

scanf("%d %d",&m,&n);

Initialize the $dp$ array with zeroes. Set all cells in the first row and first column to $1$.

memset(dp,0,sizeof(dp));
for(i = 1; i <= m; i++) dp[i][1] = 1;
for(j = 1; j <= n; j++) dp[1][j] = 1;

Recalculate the values of the $dp$ array cells, starting from the second row and the second column.

for(i = 2; i <= m; i++)
for(j = 2; j <= n; j++)
  dp[i][j] = dp[i-1][j] + dp[i][j-1];

Print the answer.

printf("%lld\n",dp[m][n]);

Java implementation

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in); 
    int m = con.nextInt();
    int n = con.nextInt();  
    long dp[][] = new long [m+1][n+1];
  
    for(int i = 1; i <= m; i++) dp[i][1] = 1;
    for(int j = 1; j <= n; j++) dp[1][j] = 1;

    for(int i = 2; i <= m; i++)
    for(int j = 2; j <= n; j++)
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    
    System.out.println(dp[m][n]);
    con.close();
  }
}

Python implementation

Read the input data.

m, n = map(int,input().split())

Declare the $dp$ list.

dp = [[0] * (n + 1) for i in range(m + 1)]

Set all cells in the first row and first column to $1$.

for i in range(1, m + 1): dp[i][1] = 1
for j in range(1, n + 1): dp[1][j] = 1

Recalculate the values of the $dp$ list cells, starting from the second row and the second column.

for i in range(2, m + 1):
  for j in range(2, n + 1):
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

Print the answer.

print(dp[m][n])