动态规划算法

| | |
字数统计: 568 | 阅读时长 ≈ 3

算法四个特点：

  1. 求一个问题的最优解
  2. 整体问题的最优解依赖于各个子问题的最优解
  3. 整体问题可以分解为若干个小问题，各个小问题之间存在重叠的更小的子问题
  4. 从上往下分析问题，从下往上求解问题。为避免重复求解子问题，用从下往上的顺序先计算小问题的最优解并存储

Leetcode (5)Longest Palindromic Substring

问题： 查找最长的回文字符串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
4
> Input: "babad"
> Output: "bab"
> Note: "aba" is also a valid answer.
>

Example 2:

1
2
3
> Input: "cbbd"
> Output: "bb"
>

解决思路：

Approach 3: Dynamic Programming

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

We define P(i,j)P(i,j) as following:
$$
P(i,j) = \begin{cases} \text{true,} &\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome}\ \text{false,} &\quad\text{otherwise.} \end{cases}
$$
Therefore,

$$
P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j )P(i,j)=(P(i+1,j−1) and Si==Sj)
$$
The base cases are:

$$
P(i, i) = trueP(i,i)=true
$$

$$
P(i, i+1) = ( S_i == S_{i+1} )P(i,i+1)=(Si==Si+1)
$$

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

Complexity Analysis

  • Time complexity : O(n^2)O(n2). This gives us a runtime complexity of O(n^2)O(n2).
  • Space complexity : O(n^2)O(n2). It uses O(n^2)O(n2) space to store the table.

Additional Exercise

Could you improve the above space complexity further and how?

代码：

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
class Solution {
public:
    string longestPalindrome(string s) {
        int sLen = s.size();
        bool* boolMatrix = new bool[sLen*sLen]; //用二维数组存储p(i,j)是否是回文数组
        memset(boolMatrix, false, sLen*sLen);
        int mi=0, mj=0;
        for(int len=0; len<sLen; ++len)
        {
            for (int i=0; i<sLen; ++i)
            {
                int j = i+len;
                if(j>=sLen) continue;
                if(len==0)
                    boolMatrix[i*sLen+j] = true;
                if(len==1)
                    if (s[i]==s[j])
                    {
                        boolMatrix[i*sLen+j] = true;
                        mi = i; mj = j;
                    }
                if(len>1)
                    if(boolMatrix[(i+1)*sLen+(j-1)] && s[i]==s[j])
                    {
                        boolMatrix[i*sLen+j] = true;
                        mi = i; mj = j;
                    }
            }
        }
        return s.substr(mi, mj-mi+1);
    }
};
Title - Artist
0:00