【C++】最长回文子串/动态规划

ACM

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

char S[maxn];

int dp[maxn][maxn];

int main()

{

    gets(S);

    int len = strlen(S), ans = 1;

    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < len; i++)

    {

        dp[i][i] = 1;

        if (i < len - 1)

        {

            if (S[i] == S[i + 1])

            {

                dp[i][i + 1] = 1;

                ans = 2;

            }

        }

    }

    // 状态转移方程

    for (int L = 3; L <= len; L++)

    {

        for (int i = 0; i + L - 1 < len; i++)

        {

            int j = i + L - 1;

            if (S[i] == S[j] && dp[i + 1][j - 1] == 1)

            {

                dp[i][j] = 1;

                ans = L;

            }

        }

    }

    cout << ans;

    system("pause");

}

核心代码

#include <bits/stdc++.h>

using namespace std;

class Solution

{

public:

    int getLongestPalindrome(string A, int n)

    {

        int maxR = 1;

        // 创建dp数组

        vector<vector<int>> dp;

        vector<int> tmp;

        tmp.insert(tmp.begin(), n, 0);

        for (int i = 0; i < n; i++)

        {

            dp.push_back(tmp);

        }

        // 边界条件

        for (int i = 0; i < n; i++)

        {

            dp[i][i] = 1;

            if (i < n - 1)

            {

                if (A[i] == A[i + 1])

                {

                    dp[i][i + 1] = 1;

                    maxR = 2;

                }

            }

        }

        // 状态转移

        for (int len = 3; len <= n; len++)

        {

            // 枚举左端点i

            for (int i = 0; i + len - 1 < n; i++)

            {

                int j = i + len - 1;

                if (A[i] == A[j] && dp[i + 1][j - 1] == 1)

                {

                    dp[i][j] = 1;

                    maxR = len;

                }

            }

        }

        return maxR;

    }

};

int main()

{

    string str;

    cin >> str;

    int n = str.length();

    Solution solution;

    cout << solution.getLongestPalindrome(str, n) << endl;

    system("pause");

}

巴特西

【C++】最长回文子串/动态规划

最新文章

热门文章