蓝桥杯零基础冲过赛-第10天

蓝桥杯零基础冲过赛-第10天

leetcode64
题目秒速：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

这道题就是典型的DP问题，状态转移就在题中（每次只能向下或者向右移动一步），只不过要注意边界，在边界处理时就把二维数字当作一维数组就可以或者在DP数组外面加一圈极大数，下面用的是前一种。
解题：
状态定义：
dp[i] [j] 为到i行j列时的最小路径和
状态转移：
dp[i] [j] = min{dp[i - 1][j] + nums[i][j], dp[i][j - 1] + nums[i][j]}
边界条件：
dp[0][0] = nums[0][0]
编码：

int minPathSum(vector>& grid) {
        int m = grid[0].size(), n = grid.size();
        vector > dp(n + 1, vector(m + 1));
        dp[1][1] = grid[0][0];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 && j > 1) dp[i][j] = dp[1][j - 1] + grid[0][j - 1];
                if (j == 1 && i > 1) dp[i][j] = dp[i - 1][1] + grid[i - 1][0];
                if (i > 1 && j > 1) dp[i][j] = min(dp[i - 1][j] + grid[i - 1][j - 1], dp[i][j - 1] + grid[i - 1][j - 1]);
            }
        }
        return dp[n][m];
    }