Розумна черепашка#1704

Розумна черепашка (Розбір)

Розглянемо двовимірний масив $d p$ , де $d p [i] [j]$ dp[i][j] представляє кількість способів, якими черепашка може дістатися з клітинки $(1, 1)$ до клітинки $(i, j)$ . Встановимо $d p [1] [1] = 1$ dp[1][1] = 1.

Черепашка може потрапити в клітинку $(i, j)$ або з клітинки $(i - 1, j)$ (i - 1, j), або з клітинки $(i, j - 1)$ (i, j - 1). Таким чином, справедливе рівняння:

d p [i] [j] = d p [i - 1] [j] + d p [i] [j - 1]

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

Спочатку обнуляємо масив $d p$ . Особлива увага приділяється обнуленню нульового рядка та нульового стовпця масиву $d p$ .

Якщо $i = 1$ i = 1, то $d p [i - 1] [j] = d p [0] [j] = 0$ dp[i - 1][j] = dp[0][j] = 0 і тоді рівняння динаміки спрощується до $d p [1] [j] = d p [1] [j - 1]$ dp[1][j] = dp[1][j - 1]. Так перераховується перший рядок.
Якщо $j = 1$ j = 1, то формула має вигляд $d p [i] [1] = d p [i - 1] [1]$ dp[i][1] = dp[i - 1][1]. Так перераховується перший стовпець.

З огляду на те, що $d p [1] [1] = 1$ dp[1][1] = 1, можна зробити висновок, що всі клітинки в першому рядку та першому стовпці будуть містити значення $1$ , що відповідає єдиному способу дістатися до кожної з цих клітинок.

Приклад

Заповнимо масив $d p$ для поля розміром $4 \times 3$ 4 \times 3:

Реалізація алгоритму

Оголосимо робочий масив $d p$ .

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

Читаємо вхідні дані.

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

Ініціалізуємо масив $d p$ нулями. У всі клітинки першого рядка та першого стовпця заносимо $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;

Перераховуємо значення клітинок масиву $d p$ , починаючи з другого рядка та другого стовпця.

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

Виводимо відповідь.

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

Java реалізація

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();
  }
}

Java

Python реалізація

Читаємо вхідні дані.

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

Оголосимо список $d p$ .

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

У всі клітинки першого рядка та першого стовпця заносимо $1$ .

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

Перераховуємо значення клітинок масиву $d p$ , починаючи з другого рядка та другого стовпця.

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(dp[m][n])