跟着灵茶山艾府大佬学习算法思路的day17（并没有在一个月内掌握hot100）
b站链接如下：
在数组的前缀或后缀上转移，这类题目一般称为线性DP，对于区间DP，我们会把问题规模缩小到数组中间的区间上，而不仅仅是前缀或后缀。
dp之所以不需要一个变量维护全局最优，因为全局最优一定由子问题最优组成。这就是dp和贪心或暴力的区别。
此外，对于递归改写递推而言，只需要保证状态转移的依赖关系满足，并有方法能遍历整个dp数组即可，顺着这条规则找遍历顺序，往往循环最后不必很复杂。
递推之所以难以思考，因为递推是自底向上的，从最小规模的子问题开始。但我们到底要从哪个子问题开始，到底要从子问题转移到哪一个上级问题，这并不是容易思考的。
最长回文子序列 题目描述：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
思路：
由于回文从右往左读和从左往右读是一样的，所以可以求s和反转后s的最长公共子序列。
还有一种思路是考虑选或不选入子序列中。由于是回文，就是第一个和最后一个同时考虑选或不选，当第一个和最后一个相等，当然都选入子序列，能被选入子序列的情形也只有这一种。
当第一个和最后一个不等时，肯定不能选，那么就要考虑排除，从LCS我们可以知道，考虑一端肯定比两端都排除更好。但要注意，同样地，没被排除的那个此时也只是备选，只有两头都相等时才能选入。
递归边界值得注意，如果递归到同一个字母，就返回1，如果没有字母，就返回0。
改写递推，需要注意的是循环顺序。因为需要满足依赖关系，在计算出fi之前需要知道fi+1，在知道fj之前需要知道fj-1，因此i需要倒序枚举，j需要正序枚举：
值得注意的是，在填入2维dp表格时，是从下到上，逐行地从左至右填表，只能填满上三角区域。因为只依赖自己下方和前面的值，所以当然也可以滚动数组。如果使用二维数组，填表顺序知道与否都不重要，但如果要使用一维优化，填表顺序也是要知道的。
这个从左至右的顺序，决定了本题不需要像有的0-1背包问题那样倒序遍历数组，而是正序遍历也能完成一维优化。
代码：
复用LCS，效率较低：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var longestPalindromeSubseq = function(s) {
const m = s.length;
const rs = s.split('').reverse().join(''); // 反转s
const n = rs.length;
const memo = Array.from({ length : m + 1 }, () => new Array(n + 1).fill(-1));
// m和n此时不必+1，dp时有了初始状态才需要+1
const dfs = (i, j) => {
if (i < 0 || j < 0) {
return 0;
}
if (memo[i][j] !== -1) {
return memo[i][j];
}
memo[i][j] = Math.max(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1) + (s[i] === rs[j] ? 1 : 0));
return memo[i][j];
}
return dfs(m - 1, n - 1);
};
递归的选或不选，超时：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var longestPalindromeSubseq = function(s) {
const m = s.length;
const dfs = (i, j) => {
if (i === j) {
return 1;
}
if (j === i - 1) {
return 0;
}
if (s[i] === s[j]) {
return dfs(i + 1, j - 1) + 2;
}
return Math.max(dfs(i + 1, j), dfs(i, j - 1));
}
return dfs(0, m - 1);
};
递归+记忆化，不管i和j是指向同一个数组还是不同数组，memo的大小只取决于参数的取值范围：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var longestPalindromeSubseq = function(s) {
const m = s.length;
const memo = Array.from({ length : m }, () => new Array(m).fill(-1));
const dfs = (i, j) => {
if (i === j) {
return 1;
}
if (j === i - 1) {
return 0;
}
if (memo[i][j] !== -1) {
return memo[i][j];
}
if (s[i] === s[j]) {
memo[i][j] = dfs(i + 1, j - 1) + 2;
return memo[i][j];
}
memo[i][j] = Math.max(dfs(i + 1, j), dfs(i, j - 1));
return memo[i][j];
}
return dfs(0, m - 1);
};
改写递推：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var longestPalindromeSubseq = function(s) {
const m = s.length;
const dp = Array.from({ length: m }, () => new Array(m).fill(0));
for (let i = m - 1; i >= 0; i--) {
dp[i][i] = 1; // 单独初始化或者套在循环里效果一样
for (let j = i + 1; j < m; j++) {
if (s[i] === s[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][m - 1];
};
一维数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var longestPalindromeSubseq = function(s) {
const m = s.length;
let dp = new Array(m).fill(0);
for (let i = m - 1; i >= 0; i--) {
dp[i] = 1;
let prev = 0;
// 更新这一大轮的dp[i+1][j-1]，同时用以保存这一大轮每一小轮的dp[i+1][j-1]（左下角）
for (let j = i + 1; j < m; j++) {
let temp = dp[j]; // 保存旧dp[j]，下一轮当prev用
if (s[i] === s[j]) {
dp[j] = prev + 2;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
// dp[i+1][j] dp[i][j-1]
}
prev = temp; // 更新下一小轮的dp[i+1][j-1]
}
}
return dp[m - 1];
};
总结：
联系LCS。递归的方程自己想很难想，但是知道之后写代码还是不难的。递推的代码也不是很好写，主要在于要想明白i和j如何更新。