一个网站源代码概多大,自由室内设计师接单网站,网站的打开速度,企业网站管理制度建设文章目录1. 题目2. 解题1. 题目
给定一个二维矩阵#xff0c;找到从上到下的最小路径。只能向左下#xff0c;下#xff0c;右下移动
所有的元素都是正整数 矩阵大小 200x200
样例 1:
输入:
1 2 3
4 5 6
7 8 9
输出:
12
解释:
最短的路径为:1-4-7, 返回12.样…
文章目录1. 题目2. 解题1. 题目
给定一个二维矩阵找到从上到下的最小路径。只能向左下下右下移动
所有的元素都是正整数 矩阵大小 200x200
样例 1:
输入:
1 2 3
4 5 6
7 8 9
输出:
12
解释:
最短的路径为:1-4-7, 返回12.样例 2:
输入:
7 1 12 1
2 3 4 2
1 10 2 6
Output:
4
解释:
最短的路径为:1-2-1, 返回 4.https://tianchi.aliyun.com/oj/338592228998370026/357527484118536805
2. 解题
每一个位置的最优值头顶上的三个元素的最小的那个 转移到该位置
class Solution {
public:/*** param matrix: * return: Return the smallest path*/int smallestPath(vectorvectorint matrix) {// Write your code hereint m matrix.size(), n matrix[0].size();vectorint dp matrix[0];for(int i 1; i m; i) {vectorint temp(n, 0);int prevmin;for(int j 0; j n; j){prevmin dp[j];if(j-1 0)prevmin min(prevmin, dp[j-1]);if(j1 n)prevmin min(prevmin, dp[j1]);temp[j] matrix[i][j] prevmin;}swap(dp, temp);}return *min_element(dp.begin(), dp.end());}
};222ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
