数据结构学习 leetcode64最小路径和

动态规划

题目：

建议看这里，有这道题详细的解析。我觉得写的挺好。

这是我在学动态规划的时候，动手做的一道题。

虽然我在学动态规划，但是我之前学了dps，所以我就想先用dps试着做，结果发现不行，原因是我的中止条件没有弄好，最终如果改成dps+memory，就会和动态规划一样了。

解析：

dp状态：【F（x，y）】走到（x，y）时所用的最小路径和。满足「最优子结构」和「无后效性」。

dp转移方程：分类讨论的思想

• 如果上边和左边都有，就找上边和左边的min
• 如果只有上边，那就上边最小路径和+（x，y）的值
• 如果只有左边，那就左边最小路径和+（x，y）的值
• 如果上边左边都没有，就保持原来的值（0，0）

复杂度计算：

时间复杂度O(n+m)
空间复杂度O(1)

代码：

这题一写就过了，太好了！

#include <vector>
//解法一：动态规划 
//最小路径和
//时间复杂度O(n+m)
//空间复杂度O(1)
class Solution {
public:int minPathSum(std::vector<std::vector<int>>& grid) {if (grid.empty() || grid[0].empty())return 0;row = grid.size();col = grid[0].size();//状态：grid[i][j]for (int i = 0; i < row; ++i){for (int j = 0; j < col; ++j){//转移方程，分类讨论if (i - 1 >= 0 && j - 1 >= 0)//上边和左边都有，就找上边和左边的mingrid[i][j] += (grid[i][j - 1] < grid[i - 1][j]) ? grid[i][j - 1] : grid[i - 1][j];else if (i - 1 >= 0)//只有上边grid[i][j] += grid[i - 1][j];else if (j - 1 >= 0)//只有左边grid[i][j] += grid[i][j - 1];}}return grid[row - 1][col - 1];}
private:int row;int col;
};void Test_solution2()
{//std::vector<std::vector<int>> grid = { {1,3,1},{1,5,1},{4,2,1} };//std::vector<std::vector<int>> grid = { {1,2,3},{4,5,6} };//std::vector<std::vector<int>> grid = { {1,2,3} };//std::vector<std::vector<int>> grid = { {1,3,1},{1,5,1},{4,2,0} };//std::vector<std::vector<int>> grid = { {3} };std::vector<std::vector<int>> grid = { {} };Solution solution;std::cout << solution.minPathSum(grid);
}