区间DP

LeetCode 516 https://leetcode.cn/problems/longest-palindromic-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 区间 DP，从大区间转移到小区间。f[i][j] 为 s[i] 到 s[j] 的最长回文子序列。 if (s[i] == s[j]) { f[i][j] = 2 + f[i + 1][j - 1]; } else { f[i][j] = max(f[i + 1][j], f[i][j - 1];) } 时间复杂度：O(n^2)，其中 n 为 s 的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的转移个数。本题中状态个数等于 O(n^2)，而单个状态的转移个数为 O(1)，因此时间复杂度为 O(n^2)。 空间复杂度：O(n^2)。 ...