废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【动态规划】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
最大正方形【MID】
来解决一道最大正方形的题目
题干
解题思路
原题解出处按照动态规划的标准解题讨论来进行解题，理解 min(上, 左, 左上) + 1，如题，在其他动态规划方法的题解中，大都会涉及到下列形式的代码：
// 伪代码 if (matrix(i , j ) == '1') { dp(i, j) = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1; }
其中，dp(i, j) 是以 matrix(i , j ) 为 右下角 的正方形的最大边长，
若某格子值为 1，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格
先来阐述简单共识
- 若形成正方形（非单 1），以当前为右下角的视角看，则需要：当前格、上、左、左上都是 1
- 可以换个角度：当前格、上、左、左上都不能受 0 的限制，才能成为正方形
上面详解了 三者取最小 的含义：
- 图 1：受限于左上的 0
- 图 2：受限于上边的 0
- 图 3：受限于左边的 0
数字表示：以此为正方形右下角的最大边长；黄色表示：格子 ? 作为右下角的正方形区域。就像 木桶的短板理论 那样——附近的最小边长，才与 ? 的最长边长有关。 此时已可得到递推公式
// 伪代码 if (grid[i][j] == '1') { dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; }
1 定义状态（定义子问题）
dp 具体定义：dp[i ][j ] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」
为何不是 dp[i][j]，回到图解中，任何一个正方形，我们都「依赖」当前格 左、上、左上三个方格的情况，但第一行的上层已经没有格子，第一列左边已经没有格子，需要做特殊 if 判断来处理，为了代码简洁，我们 假设补充 了多一行全 ‘0’、多一列全 ‘0’
2 状态转移方程（描述子问题之间的联系）
取自己左上、上方、左边最小值再加上自身
// 伪代码 if (grid[i][j] == '1') { dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; }
3 初始化状态
初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0，相当于已经计算了所有的第一行、第一列的 dp 值
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可,定义 maxSide 表示最长边长，每次得出一个 dp，就 maxSide = max(maxSide, dp); 最终返回 return maxSide * maxSide;
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ public int maximalSquare(char[][] matrix) { // 1 入参校验 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } // 2 定义最长边，以及获取边长 int maxSide = 0; int row = matrix.length; int col = matrix[0].length; // 3 定义dp数组,dp[i][j]表示以i、j为坐标的元素作为右下角的最大正方形边长，默认初始化了两列0 int[][] dp = new int[row + 1][col + 1]; // 4 编写状态转移方程 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { if (matrix[i - 1][j - 1] == '1') { dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1; maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide * maxSide; } }
考虑到每个方格都需要参与计算，双重循环要从索引1开始（否则dp[0][0]无法进行状态转移，会数组越界），这样为了第0行第0列可以参与计算，就给dp数组补了0，也就是base case，补0后dp的第1行和第1列对应的判断元素其实是matrix的第0行和第0列，所以这里的if条件是：matrix[i - 1][j - 1] == '1'
复杂度分析
时间复杂度：O(N*M)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；
空间复杂度：O(N*M)，我们使用了二维dp,所以其空间复杂度也是O(N*M)
最小路径和【MID】
再来一道类似的二维DP题，最小路径和
题干
首先还是限制在一个二维矩阵中，求最值问题很容易联想到动态规划
解题思路
既然是二维矩阵，我们需要同样定义个动态规划表来填充，这里可以通过补充边界来避免判断边界
1 定义状态（定义子问题）
dp 具体定义：dp[i ][j ] 表示 「以grid第 i-1 行、第 j -1列为结尾的路径中的最小路径和」
2 状态转移方程（描述子问题之间的联系）
既然是以grid[i][j]为结尾的最小路径和，且因为路径只能向右和向下，所以对于当前元素来说，之前的路径和就是来自于上边或者左边
3 初始化状态
// 这里默认初始化了全0的一行和一列 int[][] dp = new int[row + 1][col + 1];
为了避免判断边界条件，我们将边界补充为最大值
for (int i = 2; i <= row; i++) { dp[i][0] = Integer.MAX_VALUE; } for (int j = 2; j <= col; j++) { dp[0][j] = Integer.MAX_VALUE; }
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
最终解就是dp表的右下角dp[row][col]
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // 1 处理异常入参 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } // 2 定义dp[i][j]为以grid[i][j]元素为结尾的最小路径和 int row = matrix.length; int col = matrix[0].length; // 这里默认初始化了全0的一行和一列 int[][] dp = new int[row + 1][col + 1]; // 3 第一行和第一列填充为INT最大值 for (int i = 2; i <= row; i++) { dp[i][0] = Integer.MAX_VALUE; } for (int j = 2; j <= col; j++) { dp[0][j] = Integer.MAX_VALUE; } // 3 状态转移递推 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { // dp[i][j]为上方和左方最小路径和+当前元素的值 dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + matrix[i - 1][j - 1]; } } return dp[row][col]; } }
复杂度分析
时间复杂度：O(N*M)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；
空间复杂度：O(N*M)，我们使用了二维dp,所以其空间复杂度也是O(N*M)
不同路径【MID】
再来一道类似的二维DP题，同时也是剑指offer的经典题目
题干
和最小路径和类似，只是没有权重的概念
解题思路
和最小路径和的思路一样，也是漫游二维动规DP
1 定义状态（定义子问题）
dp 具体定义：dp[i][j] 为以i-1、j-1元素为结尾的路径总数
2 状态转移方程（描述子问题之间的联系）
走到当前元素的路径总和为从上边和左边来的路径总和之和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3 初始化状态
为了避免边界判断，对第一列和第一行进行补0，对于第一行第一列，其路径来源提供的是0
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
DP的右下角就是最终解dp[m][n]
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // 1 入参进行校验,不满足入参条件返回0 if (m < 1 && n < 1) { return 0; } // 2 定义dp数组，dp[i][j] 为以i-1、j-1元素为结尾的路径总数,初始化补0，对于第一行第一列，其路径来源提供的是0 int[][] dp = new int[m + 1][n + 1]; // 3 递推构建动态转移 for (int i = 1; i <= m; i++) { for ( int j = 1; j <= n; j++) { if (i == 1 && j == 1) { // base case，以matrix[0][0]也就是矩阵第一个元素为结尾的路径有1条 dp[i][j] = 1; } else { // 以i、j为终点的元素的路径总和为从上方来的路径+从左边来的路径总和 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m][n]; } }
复杂度分析
时间复杂度：O(N*M)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；
空间复杂度：O(N*M)，我们使用了二维dp,所以其空间复杂度也是O(N*M)
