C++ 求矩陣最短路問題最簡單最暴力的dp解法

#include <iostream>

//輸入一個矩陣數組，求出從arr[0][0]到arr[row - 1][col - 1]的最短路徑

int minPathSum(int (*arr)[10], const int &row, const int &col); //數組并不完全是指針，傳參數需要注意

int main()

{

int arr[10][10], num, row = 0, col = 0;

std::cin >> row >> col;

for (int i = 0; i < row; ++i)

{

for (int j = 0; j < col; ++j)

{

std::cin >> num;

arr[i][j] = num;

}

}

std::cout << minPathSum(arr, row, col);

system("pause");

return 0;

}

int minPathSum(int (*arr)[10], const int &row, const int &col)

{

if (arr == nullptr || row < 1 || col < 1)

return 0;

int **pArr = new int*[row];

for (int i = 0; i < row; ++i)

{

pArr[i] = new int[col];

}

//int pArr[10][10];

pArr[0][0] = arr[0][0];

for (int i = 1; i < row; ++i)

{

pArr[i][0] = arr[i][0] + pArr[i - 1][0];

}

for (int j = 1; j < col; ++j)

{

pArr[0][j] = arr[0][j] + pArr[0][j - 1];

}

for (int i = 1; i < row; ++i)

{

for (int j = 1; j < col; ++j)

{

pArr[i][j] = pArr[i - 1][j] < pArr[i][j - 1] ? pArr[i - 1][j] + arr[i][j] : pArr[i][j - 1] + arr[i][j];

}

}

return pArr[row - 1][col - 1];

}