路径问题|dp|笔记心得

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                }
                else if (i == 0) {
                    dp[i][j] = dp[i][j - 1];
                }
                else if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        //  dp[i][j]=dp[i][j-1]+dp[i-1][j]; 转移方程是没有变化的
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果不是有障碍的话
                if (obstacleGrid[i][j] == 0) {
                    if (i == 0 && j == 0) {
                        dp[i][j] = 1;
                    }
                    else if (i == 0) {
                        dp[i][j] = dp[i][j - 1];
                    }
                    else if (j == 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                    else {
                        dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // 最小路径和 对于边界点 需要单独处理一下
        int m = grid.size(), n = grid[0].size();
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                // 判断一下边界
                if (i == 0 && j == 0) {
                    // 结束了
                    continue;
                }
                else if (i == 0) {
                    grid[i][j] += grid[i][j - 1];
                }
                else if (j == 0) {
                    grid[i][j] += grid[i - 1][j];
                }
                else {
                    grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }
};

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& dp) {
        // 经典模板题目了
        int n = dp.size();
        for (int i = n - 2;i >= 0;i--) {
            for (int j = 0;j <= i;j++) {
                dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        return dp[0][0];
    }
};

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 从下往上开始走
        for (int i = n - 2;i >= 0;i--) {
            for (int j = 0;j < n;j++) {
                // 因为是三个方向 需要判断一下大小
                // 这个b和c必须设置为最大值 因为和比较的a已经不是原来的了 
                // 可能已经被干扰了
                int a = matrix[i + 1][j], b = INT_MAX, c = INT_MAX;
                if (j + 1 <= n - 1) {
                    b = matrix[i + 1][j + 1];
                }
                if (j >= 1) {
                    c = matrix[i + 1][j - 1];
                }
                matrix[i][j] += min(a, min(b, c));
            }
        }
        int ans = INT_MAX;
        for (int j = 0;j < n;j++)ans = min(ans, matrix[0][j]);
        return ans;
    }
};

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        // 拓展有同一列了
        for (int i = n - 2; i >= 0; i--) {
            // 记录最大值和最小值的索引下标
            int idx1 = -1, idx2 = -1;
            for (int k = 0; k < n; k++) {
                int cur = grid[i + 1][k];
                if (idx1 == -1 || grid[i + 1][idx1] >= cur) {
                    idx2 = idx1;
                    idx1 = k;
                }
                else if (idx2 == -1 || grid[i + 1][idx2] > cur) {
                    idx2 = k;
                }
            }
            for (int j = 0; j < n; j++) {
                grid[i][j] += idx1 == j ? grid[i + 1][idx2] : grid[i + 1][idx1];
            }
        }
        int ans = INT_MAX;
        for (int j = 0; j < n; j++) {
            ans = min(ans, grid[0][j]);
        }
        return ans;
    }
};