Ağıllı bağa#1704

Ağıllı bağa (Həll təhlili)

İkidəyişənli $d p$ massivi nəzərdən keçirək ki, $d p [i] [j]$ dp[i][j] tısbağanın $(1, 1)$ hüceyrəsindən $(i, j)$ hüceyrəsinə qədər çata biləcəyi yolların sayını göstərir. $d p [1] [1] = 1$ dp[1][1] = 1 olduğunu təsbit edək.

Tısbağa $(i, j)$ hüceyrəsinə ya $(i - 1, j)$ (i-1, j), ya da $(i, j - 1)$ (i, j-1) hüceyrəsindən gələ bilər. Beləliklə, aşağıdakı uyğunluq düzgündür:

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]

Əvvəlcə $d p$ massivini sıfırlarla doldururuq. Xüsusi diqqəti $d p$ massivinin sıfırıncı sətrinə və sıfırıncı sütununa yönəldəcəyik.

Əgər $i = 1$ i=1 olarsa, $d p [i - 1] [j] = d p [0] [j] = 0$ dp[i-1][j] = dp[0][j] = 0 və bununla, dinamik tənlik $d p [1] [j] = d p [1] [j - 1]$ dp[1][j] = dp[1][j-1] qədər sadələşir. Bu şəkildə birinci sətir yenidən hesablanır.
Əgər $j = 1$ j=1 olarsa, tənlik $d p [i] [1] = d p [i - 1] [1]$ dp[i][1] = dp[i-1][1] şəklində olur. Bu şəkildə birinci sütun yenidən hesablanır.

$d p [1] [1] = 1$ dp[1][1] = 1 olduğunu nəzərə alaraq, ilk sətirdə və ilk sütunda bütün hüceyrələrin dəyər olaraq $1$ olduğunu qəbul etmək olar ki, bu da hər bir hüceyrəyə çatmaq üçün yeganə yoldur.

Misal

$4 \times 3$ 4 \times 3 ölçülü bir sahə üçün $d p$ massivini dolduraq:

Alqoritmin həyata keçirilməsi

İşlək $d p$ massivini elan edək.

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

Giriş məlumatlarını oxuyuruq.

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

$d p$ massivini sıfırlarla ilkləndiririk. Birinci sətir və ilk sütunun bütün hüceyrələrinə $1$ yerləşdiririk.

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$ massivinin hüceyrələrinin dəyərlərini yenidən hesablayırıq, ikinci sətir və ikinci sütundan başlayaraq.

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

Cavabı çıxarırıq.

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

Java həyata keçirilməsi

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 həyata keçirilməsi

Giriş məlumatlarını oxuyuruq.

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

$d p$ siyahısını elan edək.

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

Birinci sətir və ilk sütunun bütün hüceyrələrinə $1$ yerləşdiririk.

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

$d$ massivinin hüceyrələrinin dəyərlərini yenidən hesablayırıq, ikinci sətir və ikinci sütundan başlayaraq.

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]

Cavabı çıxarırıq.

print(dp[m][n])