动态规划矩阵
接下来我们深入一下，看几道矩阵类型的题目：
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
对于每一个i,j都是到到第i-1,j和i,j-1位置的和
所以有dp[i][j]=dp[i−1][j]+dp[i][j−1]
class Solution { public: int uniquePaths(int m, int n) { int dp[m][n]; // 对于边界，到达路径只有1种可能 for (int i = 0; i < m; i++) dp[i][0] = 1; for (int i = 0; i < n; i++) dp[0][i] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } int cc = dp[m-1][n-1]; return cc; } };
64. 最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
该题目和上面的题目有异曲同工之妙
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); int dp[n][m]; dp[0][0] = grid[0][0]; for (int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + grid[i][0]; for (int i = 1; i < m; i++) dp[0][i] = dp[0][i-1] + grid[0][i]; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[n-1][m-1]; } };
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
该题目是62的进阶版，有障碍物的位置设置为不可达即可
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int n = obstacleGrid.size(); int m = obstacleGrid[0].size(); int *f = new int[m]; memset(f, 0, m * 4); f[0] = (obstacleGrid[0][0] == 0); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (obstacleGrid[i][j] == 1) { f[j] = 0; continue; } if (j -1 >=0 && obstacleGrid[i][j-1] == 0) { f[j]+=f[j-1]; } } } int val = f[m-1]; delete [] f; return val; } };
120. 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); vector<vector<int>> f(n, vector<int>(n)); f[0][0] = triangle[0][0]; for (int i = 1; i < n; ++i) { f[i][0] = f[i - 1][0] + triangle[i][0]; for (int j = 1; j < i; ++j) { f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]; } f[i][i] = f[i - 1][i - 1] + triangle[i][i]; } return *min_element(f[n - 1].begin(), f[n - 1].end()); } };
931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int n = matrix.size(); vector<vector<int>> dp(n, vector<int>(n)); // 初始化最初一行的dp copy(matrix[0].begin(), matrix[0].end(), dp[0].begin()); // 推出之后的没一个下降 // dp[i][j]=matrix[i][j]+min(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1]) for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { int mn = dp[i - 1][j]; if (j > 0) { mn = min(mn, dp[i - 1][j - 1]); } if (j < n - 1) { mn = min(mn, dp[i - 1][j + 1]); } dp[i][j] = mn + matrix[i][j]; } } return *min_element(dp[n - 1].begin(), dp[n - 1].end()); } };
221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { if (matrix.size() == 0 || matrix[0].size() == 0) return 0; int maxSide = 0; int rows = matrix.size(), columns = matrix[0].size(); vector<vector<int>> dp(rows, vector<int>(columns)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == '1') { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1; } maxSide = max(maxSide, dp[i][j]); } } } int maxSquare = maxSide * maxSide; return maxSquare; } };
