动态规划DP(Dynamic programming):通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法
DP 常适用于 有 重叠子问题 和 最优子结构性质 的问题,动态规划方法所耗时间往往低于朴素解法
基本思想
若要解一个给定的问题,需解其不同部分(即子问题),再根据子问题的解以得到原问题的解。
DP 需要注意的要素
- 明确dp二维数组表示的含义
- base case
- 状态的转移: 对于回文/LCS(最长公共子序列)之类的问题则是考虑当前字串与已经计算过的字串之间的关系
- 由状态的转移来确定 loop的边界
- 由loop的边界打出表格,可得出最后一个dp的状态值,即结果。
LeetCode 1143.最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0
- 对于s[1,…,i] t[1,…,j] LCS 长度为dp[i][j]
- base case 一个字符串和自身没有子序列 dp[0][j] = dp[i][0] = 0
s.charAt(i) = t.charAt(j) : dp[i][j] = dp[i-1][j-1] + 1 s.charAt(i) != t.charAt(j): dp[i][j] = max(dp[i-1][j],dp[i][j-1])
for i in range(n+1): for j in range(m+1):
- dp[n][m]
状态矩阵
/* j
* a b c b a
* 0 0 0 0 0 0
a 0 1 1 1 1 1
b 0 1 2 2 2 2
i c 0 1 2 3 3 3
b 0 1 2 3 4 4
c 0 1 2 3 4 4
b 0 1 2 3 4 4
a 0 1 2 3 4 5
*/
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int [][]dp = new int[n+1][m+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][0] = dp[0][j] = 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(text1.charAt(i-1) == text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Integer.Max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
}
LeetCode 115.不同的子序列
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
- 对于s[1,…,j] t[1,…,i] 在s的子序列中t出现的个数为dp[i][j]
- base case t为空串时,dp[0][j] = 1;
s.charAt(i) = t.charAt(j) : dp[i][j] = dp[i-1][j-1] + dp[i][j-1]; s.charAt(i) != t.charAt(j): dp[i][j] = dp[i][j-1]
for i in range(m+1): for j in range(n+1):
- dp[m][n]
/**
*
* * b a b g b a g
* * 1 1 1 1 1 1 1 1
* b 0 1 1 2 2 3 3 3
* a 0 0 1 1 1 1 4 4
* g 0 0 0 0 1 1 1 5
*/
public int numDistinct(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[m + 1][n + 1];
//初始化第一行
for(int j = 0; j <= n; j++){
dp[0][j] = 1;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(t.charAt(i-1) == s.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
}else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[m][n];
}
I'm so cute. Please give me money.
- 本文链接:https://wentianhao.github.io/2021/04/03/dp/
- 版权声明:本博客所有文章除特别声明外,均默认采用 许可协议。
若没有本文 Issue,您可以使用 Comment 模版新建。