Algoritmdan nazorat savollariga javoblar Algoritm nima

i x j katakga ikki hil usulda kelish mumkin:

• 
   
  

• 
  for (int i = 2; i <= n; i++) {
  
• 
  for (int j = 2; j <= m; j++) {
  
• 
  dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j];
  
• 
  }
  
• 
  }
  
• 
  cout << dp[n][m];
  

Yo’lning o’zini tiklash

• 
  int cnt = 0;
  
• 
  int cur_x = n, cur_y = m;
  
• 
  while (cur_x > 0 && cur_y > 0) {
  
• 
  cnt++;
  
• 
  x[cnt] = cur_x;
  
• 
  y[cnt] = cur_y;
  
• 
  if (cur_x > 0 && dp[cur_x][cur_y]==dp[cur_x-1][cur_y]+a[cur_x][cur_y])
  
• 
  cur_x--;
  
• 
  else
  
• 
  cur_y--;
  
• 
  }
  
• 
  for (int i = cnt; i >= 1; i--) {
  
• 
  cout << x[i] << " " << y[i] << endl;
  
• 
  } MinimumYolDinamikYolTiklash.cpp
  

Yo’l tiklash boshqa usuli

• 
  if (dp[i-1][j] < dp[i][j-1]) {
  
• 
  dp[i][j] = dp[i-1][j]+a[i][j];
  
• 
  p[i][j] = 1;
  
• 
  }
  
• 
  else {
  
• 
  dp[i][j] = dp[i][j-1]+a[i][j];
  
• 
  p[i][j] = 2;
  
• 
  }
  

Bu eng qisqa yo'lni topish va ularning har biri uchun xarajatlarni aniqlashning klassik vazifasidir. Buni, masalan, rekursiv ravishda amalga oshirish mumkin.

Muammoda berilgan misol uchun yo'llarning faqat bir qismi bu erda ko'rsatilgan. Har bir yo'l n + m tugunlarga ega bo'ladi va biz har bir (deyarli) nuqtadan ikki tomonga bora olsak, yo'llarning umumiy sonini O (2 ^ (n + m)) deb hisoblashimiz mumkin. Bu echimga mutlaqo nomuvofiq yondashuv. Ushbu yondashuvning asosiy muammosi shundaki, biz yo'lning har bir nuqtasini qayta-qayta hisoblaymiz.

A dan B gacha bo'lgan eng qisqa yo'lni topishimiz kerak. A va B o'rtasida C nuqta mavjud va biz A dan C gacha eng qisqa yo'lni hisoblab chiqdik - shuning uchun uni qayta hisoblashimiz kerakmi? - Biz har bir ishlov berilgan nuqtaga eng qisqa yo'llarni saqlaymiz - bu dinamik dasturlashning mohiyati. Nuqtaga eng qisqa yo'lning uzunligini saqlab qolish uchun biz strukturani tanishtiramiz:

#include

#include

using namespace std;
struct Cell {

int value;

int pathCost;

};
int main() {

ifstream ifst("input.txt");

ofstream ofst("output.txt");

int n, m;

ifst >> n >> m;

vector> a(n, vector(m));
for(int i = 0; i < n; ++i) {

for(int j = 0; j < m; ++j) {

ifst >> a[i][j].value;

}

}

a[0][0].pathCost = a[0][0].value;

for(int i = 1; i < n; ++i) {

a[i][0].pathCost = a[i][0].value + a[i - 1][0].pathCost;

}

for(int i = 1; i < m; ++i) {

a[0][i].pathCost = a[0][i].value + a[0][i - 1].pathCost;

}
for(int i = 1; i < n; ++i) {

for(int j = 1; j < m; ++j) {

a[i][j].pathCost = min(a[i - 1][j].pathCost, a[i][j - 1].pathCost) + a[i][j].value;

}

}

ofst << a[n - 1][m - 1].pathCost << endl;

}