一、矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int r = matrix.size();
        int c = matrix[0].size();
		//i行 j列
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(i == 0 && j > 0){//最上边
                    matrix[i][j] += matrix[i][j-1];
                }else if (j == 0 && i > 0) {//最左边
                    matrix[i][j] += matrix[i-1][j];
                }else {
                    if (i==0 && j==0) {
                        continue;//起点
                    }
                    int min_path = std::min(matrix[i][j-1], matrix[i-1][j]);//前一行或者前一列的
                    matrix[i][j] += min_path;
                }
            }
        }
        return matrix[r-1][c-1];//路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
    }
};

基本算法思想：

动态规划。创建一个二维数组dp，dp[i][j]表示从起点到达坐标(i,j)的最小路径和。初始化dp[0][0]为matrix[0][0]，然后遍历矩阵，对于每个位置(i,j)，更新dp[i][j]为dp[i-1][j]和dp[i][j-1]中的较小值加上matrix[i][j]。最后返回dp[r-1][c-1]即为最小路径和。

时间复杂度：

O(r*c)，其中r为矩阵的行数，c为矩阵的列数。

空间复杂度：

O(r*c)，需要创建一个与矩阵大小相同的二维数组dp。

二、三角形最短路径和

给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。

数据范围：三角形数组行数满足 1≤�≤200 1≤n≤200  ，数组中的值都满足 ∣���∣≤104 ∣val∣≤104 

#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param triangle int整型vector<vector<>>
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        vector<vector<int>> dp(triangle.size()+1,vector<int>(triangle.size()+1,0));
        //这个二维向量的大小是 triangle.size()+1，即 triangle 的大小加1。
        //每一个元素都是一个 vector<int>，它的大小也是 triangle.size()+1，每个元素初始化为 0。
        //i行 j列
        for (int i = triangle.size()-1; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[i][j] = min(dp[i+1][j+1], dp[i+1][j]) + triangle[i][j];
                //比较当前格子 下面的格子 和 下面的右侧格子
            }
        }
        return dp[0][0];
    }
};

基本算法思想：

动态规划。从三角形的底部开始，每一层计算出从当前位置到底部的最小路径和，最终得到从顶部到底部的最小路径和。

时间复杂度：

O(n^2)，其中 n 是三角形的行数。

空间复杂度：

O(n^2)，需要一个二维数组来存储中间状态。