Đường đi tổng nhỏ nhất trong mảng 3D (Minimum Sum Path In 3-D Array) trong C++

Cho khối lập phương 3D cube[length][breadth][height]. Tìm đường đi từ (0,0,0) đến (L-1,B-1,H-1) chỉ đi tăng chỉ số (i+1, j+1, k+1) sao cho tổng các giá trị trên đường đi nhỏ nhất.

Ví dụ

Đầu vào: Cube 3x3x3:
{ {2,4,1}, {3,4,5}, {9,8,7} },
{ {5,3,2}, {7,6,5}, {8,7,6} },
{ {3,2,1}, {4,3,2}, {5,4,3} }

Đầu ra: 15

Giải thích: Đường đi: 2→4→1→3→5 = 15.

Đầu vào: Cube 2x2x2: { {1,2}, {7,8} }, { {3,5}, {9,16} }

Đầu ra: 24 (1+2+5+16)

Phương pháp: Quy hoạch động 3D

• Tạo mảng dp cùng kích thước.
• dp[0][0][0] = cube[0][0][0].
• Khởi tạo 3 mặt phẳng biên: dp[i][0][0], dp[0][j][0], dp[0][0][k] (chỉ đi theo 1 chiều).
• Khởi tạo 3 mặt phẳng 2D: dp[i][j][0], dp[i][0][k], dp[0][j][k] (min của 2 hướng).
• Nội bộ: dp[i][j][k] = min(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]) + cube[i][j][k].
• Kết quả: dp[L-1][B-1][H-1].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
#define L 3
#define B 3
#define H 3

int Minimum(int a, int b, int c) {
    return min(a, min(b, c));
}

int Minimum_SubPath(int cube[][B][H]) {
    int dp[L][B][H];
    dp[0][0][0] = cube[0][0][0];
    for (int i=1; i

Đầu ra chương trình
Minimum Sum Path In 3-D Array: 15