LeetCode 516 Longest Palindromic Subsequence

Tag: 动态规划问题 LeetCode Posted on 2022-02-16 14:20:47 Edited on 2022-02-16 14:47:32 Views: 143

概述

https://leetcode.com/problems/longest-palindromic-subsequence/

动态规划法

极值问题,你知道我要说什么了吧?

回文子串,我们为了方便应该从起点下手

开玩笑,应该从两头下手。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), -1));
        return helper(dp, s, 0, s.size() - 1);
    }
    
    int helper(vector<vector<int>>& dp, string& s, int l, int r) {
        if (l == r) return 1;
        if (l > r) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        if (s[l] == s[r]) {
            dp[l][r] = 2 + helper(dp, s, l + 1, r - 1);
        } else {
            dp[l][r] = max(helper(dp, s, l + 1, r), helper(dp, s, l, r - 1));
        }
        return dp[l][r];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/