给定一个三维数组arr[l][m][n]，任务是找到从数组的第一个单元到数组的最后一个单元的最小路径和。我们只能遍历到相邻的元素，即从给定的单元（i，j，k），单元（i+1，j，k），（i，j+1，k）和（i，j，k+1）可以遍历，不允许对角遍历，我们可以假设所有代价都是正整数。
null
例如：
Input : arr[][][]= { {{1, 2}, {3, 4}}, {{4, 8}, {5, 2}} };Output : 9Explanation : arr[0][0][0] + arr[0][0][1] + arr[0][1][1] + arr[1][1][1]Input : { { {1, 2}, {4, 3}}, { {3, 4}, {2, 1}} };Output : 7Explanation : arr[0][0][0] + arr[0][0][1] + arr[0][1][1] + arr[1][1][1]
让我们考虑由长方体表示的三维阵列ARR〔2〕〔2〕〔2〕，其值为：
arr[][][] = {{{1, 2}, {3, 4}}, { {4, 8}, {5, 2}}};Result = 9 is calculated as:
![图片[1]-三维阵列中的最小和路-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_SumPathIn3-D.png)
这个问题类似于 最小成本路径。 可以用动态规划来解决。
// Array for storing resultint tSum[l][m][n];tSum[0][0][0] = arr[0][0][0];/* Initialize first row of tSum array */for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i-1][0][0] + arr[i][0][0];/* Initialize first column of tSum array */for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j-1][0] + arr[0][j][0];/* Initialize first width of tSum array */for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k-1] + arr[0][0][k];/* Initialize first row- First column of tSum array */for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i-1][j][0], tSum[i][j-1][0], INT_MAX) + arr[i][j][0];/* Initialize first row- First width of tSum array */for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i-1][0][k], tSum[i][0][k-1], INT_MAX) + arr[i][0][k];/* Initialize first width- First column of tSum array */for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k-1], tSum[0][j-1][k], INT_MAX) + arr[0][j][k];/* Construct rest of the tSum array */for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i-1][j][k], tSum[i][j-1][k], tSum[i][j][k-1]) + arr[i][j][k];return tSum[l-1][m-1][n-1];
C++
// C++ program for Min path sum of 3D-array #include<bits/stdc++.h> using namespace std; #define l 3 #define m 3 #define n 3 // A utility function that returns minimum // of 3 integers int min( int x, int y, int z) { return (x < y)? ((x < z)? x : z) : ((y < z)? y : z); } // function to calculate MIN path sum of 3D array int minPathSum( int arr[][m][n]) { int i, j, k; int tSum[l][m][n]; tSum[0][0][0] = arr[0][0][0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i-1][0][0] + arr[i][0][0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j-1][0] + arr[0][j][0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k-1] + arr[0][0][k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i-1][j][0], tSum[i][j-1][0], INT_MAX) + arr[i][j][0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i-1][0][k], tSum[i][0][k-1], INT_MAX) + arr[i][0][k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k-1], tSum[0][j-1][k], INT_MAX) + arr[0][j][k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i-1][j][k], tSum[i][j-1][k], tSum[i][j][k-1]) + arr[i][j][k]; return tSum[l-1][m-1][n-1]; } // Driver program int main() { int arr[l][m][n] = { { {1, 2, 4}, {3, 4, 5}, {5, 2, 1}}, { {4, 8, 3}, {5, 2, 1}, {3, 4, 2}}, { {2, 4, 1}, {3, 1, 4}, {6, 3, 8}} }; cout << minPathSum(arr); return 0; } |
JAVA
// Java program for Min path sum of 3D-array import java.io.*; class GFG { static int l = 3 ; static int m = 3 ; static int n = 3 ; // A utility function that returns minimum // of 3 integers static int min( int x, int y, int z) { return (x < y)? ((x < z)? x : z) : ((y < z)? y : z); } // function to calculate MIN path sum of 3D array static int minPathSum( int arr[][][]) { int i, j, k; int tSum[][][] = new int [l][m][n]; tSum[ 0 ][ 0 ][ 0 ] = arr[ 0 ][ 0 ][ 0 ]; /* Initialize first row of tSum array */ for (i = 1 ; i < l; i++) tSum[i][ 0 ][ 0 ] = tSum[i- 1 ][ 0 ][ 0 ] + arr[i][ 0 ][ 0 ]; /* Initialize first column of tSum array */ for (j = 1 ; j < m; j++) tSum[ 0 ][j][ 0 ] = tSum[ 0 ][j- 1 ][ 0 ] + arr[ 0 ][j][ 0 ]; /* Initialize first width of tSum array */ for (k = 1 ; k < n; k++) tSum[ 0 ][ 0 ][k] = tSum[ 0 ][ 0 ][k- 1 ] + arr[ 0 ][ 0 ][k]; /* Initialize first row- First column of tSum array */ for (i = 1 ; i < l; i++) for (j = 1 ; j < m; j++) tSum[i][j][ 0 ] = min(tSum[i- 1 ][j][ 0 ], tSum[i][j- 1 ][ 0 ], Integer.MAX_VALUE) + arr[i][j][ 0 ]; /* Initialize first row- First width of tSum array */ for (i = 1 ; i < l; i++) for (k = 1 ; k < n; k++) tSum[i][ 0 ][k] = min(tSum[i- 1 ][ 0 ][k], tSum[i][ 0 ][k- 1 ], Integer.MAX_VALUE) + arr[i][ 0 ][k]; /* Initialize first width- First column of tSum array */ for (k = 1 ; k < n; k++) for (j = 1 ; j < m; j++) tSum[ 0 ][j][k] = min(tSum[ 0 ][j][k- 1 ], tSum[ 0 ][j- 1 ][k], Integer.MAX_VALUE) + arr[ 0 ][j][k]; /* Construct rest of the tSum array */ for (i = 1 ; i < l; i++) for (j = 1 ; j < m; j++) for (k = 1 ; k < n; k++) tSum[i][j][k] = min(tSum[i- 1 ][j][k], tSum[i][j- 1 ][k], tSum[i][j][k- 1 ]) + arr[i][j][k]; return tSum[l- 1 ][m- 1 ][n- 1 ]; } // Driver program public static void main (String[] args) { int arr[][][] = { { { 1 , 2 , 4 }, { 3 , 4 , 5 }, { 5 , 2 , 1 }}, { { 4 , 8 , 3 }, { 5 , 2 , 1 }, { 3 , 4 , 2 }}, { { 2 , 4 , 1 }, { 3 , 1 , 4 }, { 6 , 3 , 8 }} }; System.out.println ( minPathSum(arr)); } } // This code is contributed by vt_m |
C#
// C# program for Min // path sum of 3D-array using System; class GFG { static int l = 3; static int m = 3; static int n = 3; // A utility function // that returns minimum // of 3 integers static int min( int x, int y, int z) { return (x < y) ? ((x < z) ? x : z) : ((y < z) ? y : z); } // function to calculate MIN // path sum of 3D array static int minPathSum( int [,,]arr) { int i, j, k; int [ , , ]tSum = new int [l, m, n]; tSum[0, 0, 0] = arr[0, 0, 0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i, 0, 0] = tSum[i - 1, 0, 0] + arr[i, 0, 0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0, j, 0] = tSum[0, j - 1, 0] + arr[0, j, 0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0, 0, k] = tSum[0, 0, k - 1] + arr[0, 0, k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i, j, 0] = min(tSum[i - 1, j, 0], tSum[i, j - 1, 0], int .MaxValue) + arr[i, j, 0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i, 0, k] = min(tSum[i - 1, 0, k], tSum[i, 0, k - 1], int .MaxValue) + arr[i, 0, k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0, j, k] = min(tSum[0, j, k - 1], tSum[0, j - 1, k], int .MaxValue) + arr[0, j, k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i, j, k] = min(tSum[i - 1, j, k], tSum[i, j - 1, k], tSum[i, j, k - 1]) + arr[i, j, k]; return tSum[l-1,m-1,n-1]; } // Driver Code static public void Main () { int [, , ]arr= {{{1, 2, 4}, {3, 4, 5}, {5, 2, 1}}, {{4, 8, 3}, {5, 2, 1}, {3, 4, 2}}, {{2, 4, 1}, {3, 1, 4}, {6, 3, 8}}}; Console.WriteLine(minPathSum(arr)); } } // This code is contributed by ajit |
Javascript
<script> // Javascript program for Min // path sum of 3D-array var l = 3; var m = 3; var n = 3; // A utility function // that returns minimum // of 3 integers function min(x, y, z) { return (x < y) ? ((x < z) ? x : z) : ((y < z) ? y : z); } // function to calculate MIN // path sum of 3D array function minPathSum(arr) { var i, j, k; var tSum = Array(l); for ( var i = 0; i<l;i++) { tSum[i] = Array.from(Array(m), ()=>Array(n)); } tSum[0][0][0] = arr[0][0][0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i - 1][0][0] + arr[i][0][0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j - 1][0] + arr[0][j][0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k - 1] + arr[0][0][k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i - 1][j][0], tSum[i][j - 1][0], 1000000000) + arr[i][j][0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i - 1][0][k], tSum[i][0][k - 1], 1000000000) + arr[i][0][k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k - 1], tSum[0][j - 1][k], 1000000000) + arr[0][j][k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i - 1][j][k], tSum[i][j - 1][k], tSum[i][j][k - 1]) + arr[i][j][k]; return tSum[l-1][m-1][n-1]; } // Driver Code var arr= [[[1, 2, 4], [3, 4, 5], [5, 2, 1]], [[4, 8, 3], [5, 2, 1], [3, 4, 2]], [[2, 4, 1], [3, 1, 4], [6, 3, 8]]]; document.write(minPathSum(arr)); </script> |
输出：
20
时间复杂性： O（l*m*n） 辅助空间： O（l*m*n）
本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
