数据结构学习 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)//上边和左边都有，就找上边和左边的min
                    grid[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);
}