fucking-algorithm
fucking-algorithm copied to clipboard
动态规划之子序列问题解题模板 :: labuladong的算法小抄
打卡,感谢楼主!
自顶向下的带备忘录的递归解法。
dp 函数的定义是:在子串 s[i..j] 中,最长回文子序列的长度为 dp(s, i, j)。
Java版
class Solution {
/**
* 动态规划解题套路框架。
* 提供我总结的一个思维框架,辅助你思考状态转移方程:
* 明确 base case -> 明确「状态」 -> 明确「选择」 -> 定义 dp 数组/函数的含义。
*
* 基本思路
* 1、确定 base case。
* 2、确定「状态」,也就是原问题和子问题中会变化的变量。
* 3、确定「选择」,也就是导致「状态」产生变化的行为。
* 4、明确 dp 函数/数组的定义。
*
* 自顶向下的带备忘录的递归解法
*/
public int longestPalindromeSubseq(String s) {
int n = s.length();
// 备忘录,初始化为 -1
memo = new int[n][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
// 整个 s 的最长回文子序列长度
return dp(s, 0, n - 1);
}
// 备忘录
int[][] memo;
// dp 函数的定义是:在子串 s[i..j] 中,最长回文子序列的长度为 dp(s, i, j)。
int dp(String s, int i, int j) {
int n = s.length();
if (i < 0 || i >= n || j < 0 || j >= n) {
return 0;
}
// 查备忘录,防止重复计算
if (memo[i][j] != -1) {
return memo[i][j];
}
// 状态转移方程
if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = dp(s, i + 1, j - 1) + 1;
} else {
memo[i][j] = Math.max(
dp(s, i + 1, j),
dp(s, i, j - 1)
);
}
return memo[i][j];
}
}
可以转化为求和自己倒序序列的最长子序列
麻烦问一下 备忘录解法 为什么用的是 dp(s, i + 1, j - 1) + 1; 而不是 dp(s, i + 1, j - 1) + 2
贴一下我的理解 python版本
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
if not s:
return 0
length = len(s)
# 备忘录
# 字符串s在[i, j]范围内最长的回文子序列的长度为memo[i][j]
memo = [[0] * length for _ in range(length)]
def dp(i, j):
if (i<0) or (j<0) or (i>=length) or (j>=length) or (i>j):
# 越界情况
return 0
if i == j:
return 1
if memo[i][j]:
# 备忘录中有结果的话 使用备忘录
return memo[i][j]
# 开始条件判断
if s[i] == s[j]:
# 可以这么理解
# 假设有索引 i i+1 i+2 ..... j-1 j
# 如果s[i] == s[j], 那么 memo[i][j] = memo[i+1][j-1] + 2
memo[i][j] = dp(i+1, j-1) + 2
else:
memo[i][j] = max(
# 还可以这么理解
# 假设有索引 i i+1 i+2 ..... j-1 j
# 如果 s[i] != s[j], 那么 memo[i][j] = max(memo[i][j-1], memo[i+1][j])
# 加入s[i]
dp(i, j-1),
# 加入s[j]
dp(i+1, j)
)
return memo[i][j]
return dp(0, length-1)
对啊为什么dp函数和dp数组,当i,j相同时一个加1 一个加2啊
转化为传统的 i j 的下标, 这样判断回文比较直观
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];//dp[i][j] s[i..j] 中最长回文子序列的长度
for(int i = 0; i < n; i++){
dp[i][i] = 1;
}
for(int len = 2 ; len<= n; len++){
for(int i = 0; i+len - 1 < n ; i++){
int j = i + len -1;
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;//向两边打开
}else{
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
让字符串成为回文串的最少插入次数,贴一个精简的从顶向下的C++。跟着东哥做了不少DP,感觉还是从顶向下带个备忘录更简单一点,有一些图的问题从base case出发自底向上更好
class Solution {
vector<vector<int>> memo;
public:
// 返回s[i, j] 变成回文串的最少插入次数
int dp(string& s, int i, int j) {
// base case
if (i >= j) return 0;
if (memo[i][j] != -1) return memo[i][j];
if (s[i] == s[j]) return memo[i][j] = dp(s, i + 1, j - 1);
else return memo[i][j] = min(dp(s, i + 1, j), dp(s, i, j - 1)) + 1;
}
int minInsertions(string s) {
int n = s.size();
memo.assign(n, vector<int> (n, -1));
return dp(s, 0, n - 1);
}
};
楼上那位朋友这里这里加的是1
if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = dp(s, i + 1, j - 1) + 1;
这是因为他的base case设置的问题:
int n = s.length();
if (i < 0 || i >= n || j < 0 || j >= n) {
return 0;
}
实际上i
不可能小于0,j
也不可能在右边越界,所以base case相当于
int n = s.length();
if (i >= n || j < 0) {
return 0;
}
当i
在右边越界,或者j
在左边越界,其实相当于是把整个字符串走了两遍,因为实际上,只要i >= j
时,整个字符串就已经走完,扫了一遍,所以memo[i][j] = dp(s, i + 1, j - 1) + 1;
加一其实是2/2
,或者这里也可以写成加二,但是最后返回的结果在除以二
但是需要注意不能在递归函数中除以二,而需要在调用递归函数的主函数除以二,代码被我简单修改后如下:
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
memo = new int[n][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
// 在这里将结果除以2
return dp(s, 0, n - 1) / 2;
}
int[][] memo;
int dp(String s, int i, int j) {
int n = s.length();
if (i >= n || j < 0) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = dp(s, i + 1, j - 1) + 2;
} else {
memo[i][j] = Math.max(
dp(s, i + 1, j),
dp(s, i, j - 1)
);
}
// 不能在这里将结果除以2
return memo[i][j];
}
}
但是实际上就像我上面说的,这个算法相当于扫了两边字符串,其实当i >= j
时就可以停下,这个思路的java代码如下:
class Solution {
public int longestPalindromeSubseq(String s) {
memo = new int[s.length()][s.length()];
for (int[] ints : memo) {
Arrays.fill(ints, Integer.MIN_VALUE);
}
return process(s.toCharArray(), 0, s.length() - 1);
}
int[][] memo;
public int process(char[] s, int left, int right) {
if (left > right) {
return 0;
} else if (left == right) {
return 1;
}
if (memo[left][right] != Integer.MIN_VALUE) {
return memo[left][right];
}
if (s[left] == s[right]) {
memo[left][right] = process(s, left + 1, right - 1) + 2;
} else {
memo[left][right] = Math.max(
process(s, left + 1, right),
process(s, left, right - 1)
);
}
return memo[left][right];
}
}
left
就是上面的i
,right
就是上面的j
,如果看不习惯可以自己改一下。需要说明的是left == right
这种情况不能返回0,需要返回1,所以base case中多了一个 else if
这个写法和上面的一样,都是从左右两边向中间缩,区别就在于这个只扫了一遍字符串,所以在力扣提交时也能看到时间有差距
我自己在刚开始看这篇文章时,东哥没有给出备忘录解法,所以来看评论区,这里是加一,东哥那里是加二,导致我自己懵逼了很久,希望我这里能够帮到大家,使后来者不需要再踩坑。当然由于我水平有限可能会有一些错误,也希望大家能够指出
最后也想请教,这道题目的写法是否能够从中间往两侧扩?上面的写法都是从两侧往中间缩,自己水平有限尝试了很久也没写出来
1312 java dp 压缩版
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[] dp = new int[n];
// int[][] dp = new int[n][n];
// for(int i = 0; i < n; i++) {
// dp[i] = 1;
// // dp[i][i] = 1;
// }
for (int i = n-1; i >= 0; i--) {
int pre = 0;
for ( int j = i+1; j <n ; j++) {
int temp = dp[j];
if(s.charAt(i) == s.charAt(j)) {
dp[j] = pre;
// dp[i][j] = dp[i+1][j-1] +2;
} else {
dp[j] = Math.min(dp[j], dp[j-1])+1;
// dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
pre = temp;
}
}
return dp[n-1];
}
}