Leetcode Q64 Cpp
💡 记录刷题过程 Leetcode 第64题 c++
问题描述
错误回顾
当时我第一反应其实没想到dp，反而是往dfs+贪心的方向上去想。
也说不准为啥这里要用dp，但是思维上接受dp之后，就觉得这道题目用dp写就真的很优雅，也就想不到别的思路了
题目分析
对于每个点而言，它只能通过上边或左边的点抵达。因此，如果现在要求抵达某个点的最短路径长度，则是上边或者左边的较小值，与本身路径的长度之和。满足最优子结构。
在此DP任务中，我们需要用到的是和原二维表一样大小的二维表来存储数据。
时间复杂度
全部点都遍历且只遍历一遍，因此时间复杂度是O(m*n)
价值
- 熟悉二维vector的使用
- 作为dp的入门题目，感受了dp的魅力。