动态规划中心思想并不是很难，但是由于他的巧妙性，我们总是对题目束手无策，所以不同于其他算法题，要想真正搞懂动态规划，咱们要从经典例题入手，并归纳经验，这样，即使你看到新套路还是冥思苦想，但是咱们已经掌握的套路，足够你应付笔试面试啦。
最长回文子序列【二维dp的代表】
废话不多说，先来一道 medium 试试身手
这道题很容易理解，就是找出字符串中最大的回文字符串，当然了我们使用暴力破解去枚举所有字串，但是这样做必然费时。那我们用一个dp表去记录已有结果然后推出当前结论。这里就是最巧面的地方了，怎么去找出已有结果和当前结果的关系呢？可以参考下图：
首先是最基本的表示法，和 base 情况:
再来是一般情况的示意图:
也就是当 J-I>=3的时候 我们要依赖之前记录的结果了
代码贴出来大家体会一下：
func longestPalindrome(s string) string {l := len(s)dp := make([][]bool, l)for i := range dp {dp[i] = make([]bool, l)}max := 1maxStr := s[0:0]for j := 1; j < l; j++ {for i := 0; i < j; i++ {if j-i < 3 {dp[j][i] = s[i] == s[j]} else {dp[j][i] = (s[i] == s[j]) && dp[j-1][i+1]}if dp[j][i] {if j-i+1 > max {max = j - i + 1maxStr = s[i : j+1]}}}}return maxStr}
力扣64 最小路径和【二维dp典型例题】
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
if(m == 0)
return 0;
int n = grid[0].size();
if(n == 0)
return 0;
for(int i = 1; i < m; i++)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for(int j = 1; j < n; j++)
grid[0][j] = grid[0][j - 1] + grid[0][j];
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
return grid[m - 1][n - 1];
}
};
时间复杂度O(N ^ 2)
空间复杂度O(1)
力扣1277 统计全为1的正方形子矩阵【二维dp典型例题】
对于二维表的问题，通常可以创建另一张二维表来帮助解决问题，创建另外一张二维表的关键是需要明确创建表数据的顺序及与其前一个数据的关系，在一维列表中，如果我们是从左往右创建一维dp列表，需要知道的是新建的当前数据是这个数据之前的那些数据的关系，而在二维表中，如果是从左上角往右下角创建，则需要知道当前数据和这个数据左上角方向上的数据的关系，回到这道题来看，对于dp[i][j]则是查看其与dp[i-1][j], dp[i][j-1], dp[i-1][j-1]的关系。
1277. 统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
提示：
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix[0].size();
if(col == 0)
return 0;
vector<vector<int>>A(row, vector<int>(col, 0));
A[0][0] = matrix[0][0];
int ret = A[0][0];
for(int i = 1; i < row; i++)
{
A[i][0] = matrix[i][0];
ret += A[i][0];
}
for(int j = 1; j < col; j++)
{
A[0][j] = matrix[0][j];
ret += A[0][j];
}
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
if(matrix[i][j] == 0)
A[i][j] = 0; //如果当前值为0则肯定无法构建成正方形
else
A[i][j] = 1 + min({A[i-1][j], A[i][j-1], A[i-1][j-1]});
ret += A[i][j];
}
}
return ret;
}
};
力扣1035 不相交的线【二维dp应用题】
这道题一开始我还真没想到是采用动态规划的方法去做，直到做不出的时候才隐约感到可能是动态规划，因为它可以形成一张二维表，而且对于当前值也是采用判断的方法和之前值的方法来决定最终值是什么。最后看了看其他人的题解才明白应该如何去做。
1035. 不相交的线
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
以这种方法绘制线条，并返回我们可以绘制的最大连线数。
示例 1：输入：A = [1,4,2], B = [1,2,4]
输出：2
解释：
我们可以画出两条不交叉的线，如上图所示。
我们无法画出第三条不相交的直线，因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
示例 2：
输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出：3
示例 3：
输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出：2
提示：
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/uncrossed-lines
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int sizeA = A.size();
int sizeB = B.size();
if(sizeA == 0 || sizeB == 0)
return 0;
vector<vector<int>>dp(sizeA + 1, vector<int>(sizeB + 1, 0));
for(int i = 1; i <= sizeA; i++)
{
for(int j = 1; j <= sizeB; j++)
{
dp[i][j] = A[i-1] == B[j - 1]? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[sizeA][sizeB];
}
};
这位大神还给出了一维dp，我没有看懂，姑且先贴出来
def maxUncrossedLines(self, A, B):
m, n = len(A), len(B)
dp = [0] * (n + 1)
for i in xrange(m):
for j in range(n)[::-1]:
if A[i] == B[j]: dp[j+1] = dp[j] + 1
for j in range(n):
dp[j+1] = max(dp[j+1],dp[j])
return dp[n]
力扣72 编辑距离【二维dp应用题】
72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2：
输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minDistance(string word1, string word2) {
int word1size = word1.size();
int word2size = word2.size();
vector<vector<int>>cost(word1size + 1, vector<int>(word2size+1));
for(int i = 0; i <= word1size; i++)
cost[i][0] = i;
for(int i = 1; i <= word2size; i++)
cost[0][i] = i;
for(int i = 0; i < word1size; i++)
{
for(int j = 0; j < word2size; j++)
{
if(word1[i] == word2[j])
cost[i+1][j+1] = cost[i][j];
else
{
int a = cost[i][j];
int b = cost[i][j+1];
int c = cost[i+1][j];
cost[i+1][j+1] = a < b ? (a < c ? a : c) : (b < c ? b : c);
cost[i+1][j+1]++;
}
}
}
return cost[word1size][word2size];
}
};
力扣1029 两地调度【二维dp应用题】
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
示例：
输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-city-scheduling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int N = costs.size() / 2;
vector<vector<int>>dp(N+1, vector<int>(N+1, 0));
for(int i = 1; i <= N; i++)
dp[i][0] = dp[i-1][0] + costs[i-1][0];
for(int j = 1; j <= N; j++)
dp[0][j] = dp[0][j-1] + costs[j-1][1];
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
dp[i][j] = min(dp[i-1][j] + costs[i+j-1][0], dp[i][j-1] + costs[i + j - 1][1]);
}
return dp[N][N];
}
};
1.先假设全部飞到B市的话（并没有真的飞！！不是先到B再从B到A），再选择N人转飞到A市，那么这N个人的多花了price_A - price_B 的费用
2.因此最优的方案是，选出 price_A - price_B 最小的 NN 个人，让他们飞往 A 市，其余人飞往 B 市
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs, int res = 0) {
sort(costs.begin(), costs.end(), [](vector<int>&v1, vector<int>&v2){
return (v1[0] - v1[1] < v2[0] - v2[1]);
});
for(auto i = 0; i < costs.size() / 2; i++){
res += costs[i][0] + costs[i+costs.size()/2][1];
}
return res;
}
};
力扣518 零钱兑换II【一维dp应用题】
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
动态规划的典型模版是
- 定义答案显而易见的基本情况。
- 制定根据简单的情况计算复杂情况的策略。
- 将此策略链接到基本情况。
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0)
return 1;
if(coins.size() == 0)
return 0;
vector<int>dp(amount + 1, 0);
dp[0] = 1;
for(int i = 0; i < coins.size(); i++)
{
for(int j = coins[i]; j <= amount; j++)
{
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
时间复杂度：O（N x amount）。其中N为coins数组的长度
空间复杂度：O（amount），dp数组使用的空间
力扣174 地下城游戏 【二维dp应用题】
这道题我依旧没有解出来，在评论区有一个答案比较有意思，依旧采用的是二维dp的方法，不过它不是从左上角往右下角走，而是反过来，从右下角往左上角走。
174. 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dungeon-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row = dungeon.size();
int col = dungeon[0].size();
vector<vector<int>>dp(row + 1, vector<int>(col + 1, INT_MAX));
dp[row][col-1] = 1;
dp[row-1][col] = 1;
for(int i = row - 1; i >= 0; i--)
{
for(int j = col - 1; j >= 0; j--)
{
int need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
dp[i][j] = need > 0 ? need : 1;
}
}
return dp[0][0];
}
};
力扣96 不同的二叉搜索树【一维dp应用题】
96. 不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int numTrees(int n) {
int* dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++)
{
int tmp = 0;
for (int index = 0; index < i; index++)
{
tmp += (dp[index] * dp[i - index - 1]);
}
dp[i] = tmp;
}
return dp[n];
}
};
力扣279 完全平方数【一维dp应用题】
279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int numSquares(int n) {
if(n == 0)
return 0;
vector<int>square(n+1, INT_MAX);
square[0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j * j <= i; j++)
{
square[i] = min(square[i], square[i - j*j] + 1);
}
}
return square[n];
}
};
力扣62 不同路径【二维dp应用题】
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
当看到二维表格的时候，首先想到的就是构建二维dp表，找出各自之间的相互关系，这道题就解出来了。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m, vector<int>(n, 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];
}
return dp[m-1][n-1];
}
};
力扣63 不同路径II【二维dp应用题】
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<int>>dp(row, vector<int>(col, 0));
if(obstacleGrid[0][0] == 0)
dp[0][0] = 1;
else
return 0;
for(int i = 1; i < row; i++)
{
if(obstacleGrid[i][0] == 1)
{
for(int j = i; j < row; j++)
dp[j][0] = 0;
break;
}
else
{
dp[i][0] = 1;
}
}
for(int i = 1; i < col; i++)
{
if(obstacleGrid[0][i] == 1)
{
for(int j = i; j < col; j++)
dp[0][j] = 0;
break;
}
else
{
dp[0][i] = 1;
}
}
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
if(obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[row-1][col-1];
}
};
若有收获，就点个赞吧
0 人点赞
