Anh em nào rảnh giải giúp em cái câu này

thuật toán thế này nhé:
đầu tiên từ vị trí ban đầu. bạn xét 3 vị trí là phải, dưới và chéo. xem giá trị của cái nào là bé nhất thì đi tới vị trí số bé nhất đó. sau đó từ vị trí vừa tìm dc lại xét lại như trên. TH mà đã đi tới cuối ở 2 bên thì chỉ đi về 1 hướng thôi

Bạn đã làm thử theo hướng nào rồi?

em có 2 bài code tưởng tự vậy.
1 cái là đi từ trái qua phải. và 1 cái đi từ trên xuống dưới. củng kiểm tra 3 ô.

cái code này là đi từ trái qua pải 1 hướng em làm dc

dsd.PNG827x565 15.7 KB

int thamlam(int a[][MAX], int n, int path[]) {
	int max, tong;
	max = a[0][0];
	int vtdau;
	int vt;
	for (int i = 1; i < n; i++)
	{
		int j = 0;
		if (a[i][j] >= max)
		{
			max = a[i][j];
			vtdau = i;
		}
	}
	path[0] = vtdau;
	tong = max;
	int dem = 1;
	int i = vtdau;
	for (int j = 0; j < n - 1; j++)
	{
		max = sosanh(a[i + 1][j + 1], a[i][j + 1], a[i - 1][j + 1]);
		if (a[i + 1][j + 1] == max) vt = i + 1;
		if (a[i][j + 1] == max) vt = i;
		if (a[i - 1][j + 1] == max) vt = i - 1;
		path[dem] = vt;
		dem++;
		tong += max;
		i = vt;
	}
	return tong;
}

còn cái code này là đi trừ trên xuống dưới

dsd.PNG800x317 13.5 KB

void thamlam(int b[][20], int d, int path1[])
{
	int col;
	path1[0] = b[0][(d * 2 - 1) / 2];
	col = (d * 2 - 1) / 2;
	int max = col - 1;
	for (int i = 1; i<d; i++) {
		for (int j = -1; j <= 1; j++)
		{
			if (b[i][col + j] > b[i][max] && col + j >= 0 && col + j<(d * 2 - 1))
			{
				max = col + j;
			}
		}
		path1[i] = b[i][max];
		col = max;
	}
}

Nhưng em ko piết kết hợp sao để làm ra cài bài kia cả.

Ý tưởng tạo thêm dòng N và cột N, đặt gía trị trên cột và dòng này bằng MAX_INT -> í là lúc xét khi đến biên N-1 thì không bị đi ra ngoài vì gía trị này luôn lớn hơn ô trong bảng thật, từ vị trí ô (i,j) => xét 3 vị trí (i,j+1),(i+1,j),(i+1,j+1) thằng nào nhỏ thất thì đến, khi đến ô (N-1,N-1) thì thôi

Bài này cần gì tham lam nhỉ bạn có thể làm bằng cách Dijkstra +priority_queue độ phức tạp chỉ là ở(n^2)
F[i][j] là đường đi min đến ô i,j
Bắt đầu bằng ô 0,0 push vào queue , mỗi bước lấy phần tử top của queue ( có giá trị f[i][j] min) để update các ô (i+1,j) (j+1,i) và (i+1,j+1) rồi push các ô này vào queue.

A_ij là giá trị ở ô ij
F_ij là kết quả tốt nhất tới ô ij
Do từ ô khác tới ô ij chỉ có 3 ô (i-1,j-1) , (i,j-1), (i-1,j) nên kết quả tốt nhất ở ô ij là
F_ij=min(F_i,j-1,F_i-1,j-1,F_i-1,j)+A_ij
Từ đó ta có công thức QHD của bài toán