NC 矩阵的最小路径和
系列文章目录
文章目录
- 系列文章目录
- 前言
前言
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。
描述
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
所选择的最小累加和路径如下图所示：
int res = INT_MAX; // 定义全局变量，作为最终结果返回class Solution {
public:/**** @param matrix int整型vector<vector<>> the matrix* @return int整型*/int row, col;int minPathSum(vector<vector<int> >& matrix) {// 此方式定义数组不需要在递归函数中作为参数传入，节省栈空间row = matrix.size();col = matrix[0].size();backtracking(0, 0, 0, matrix);return res;}void backtracking(int curRow, int curCol, int curSum, vector<vector<int> >& matrix) {// 递归终止条件if (curRow == row || curCol == col)return;// 更新当前路径和curSum += matrix[curRow][curCol];// 递归终止条件if (curRow == row - 1 && curCol == col - 1) {if (curSum < res) {res = curSum;}curSum -= matrix[curRow][curCol];return;}// 开始递归backtracking(curRow + 1, curCol, curSum, matrix);backtracking(curRow, curCol + 1, curSum, matrix);// 重置当前路径和curSum -= matrix[curRow][curCol];}
};