###### tags: `LeetCode` `Dynamic Programming` `DP`

# 0005. Longest Palindromic Substring (Medium)
耗時：62 分鐘 (看Hint，知道是DP所以多凹12分鐘)

## 題目
Given a string s, return the longest palindromic substring in s.

## 思路
1. DP題，以"ababc"來舉例，當From等同於End時，
`DP[from][end] = (DP[from-1][end-1] != 0) ? DP[from+1][end-1] + 2 : -1`
(-1是用來方便判斷用的數字)

| From(down) \ End(right) | a | b | a | c | b |
| ----------------------- | --- | ----- | ------- | --- | --- |
| a | 1 | -1 | 3 (1+2) | -1 | -1 |
| b | 0 | **1** | -1 | -1 | -1 |
| a | | 0 | 1 | -1 | -1 |
| b | | | 0 | 1 | -1 |
| c | | | | 0 | 1 |

2. 以"abba"為例，當找到第0個字元'a'與第3個字元'a'時，此時去查看第1到第2個字元的最長迴文長度(為2)
則就可以得出`DP[0][3] = DP[1][2] + 2 => 4`

* Time Complexity：O(n^2)
* Space Complexity：O(n^2)

### 程式碼
(雖然通過，但耗時與空間使用量都偏後段)

class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        int longest_len = 1;
        int lengths[1000][1000] = {0};
        
        ans = s.substr(0, 1);
        for (int i = 0; i < s.length(); ++i)
            lengths[i][i] = 1;
        
        for (int bias = 1; bias < s.length(); ++bias) {
            for (int row = 0, col = 0 + bias; row < s.length(), col < s.length(); ++row, ++col) {
                if (s[row] == s[col] && lengths[row+1][col-1] != -1) {
                    lengths[row][col] = lengths[row+1][col-1] + 2;
                    if (lengths[row][col] > longest_len) {
                        longest_len = lengths[row][col];
                        ans = s.substr(row, longest_len);
                    }
                }
                else
                    lengths[row][col] = -1;
            }
        }
        
        cout << longest_len << endl;
       
        
        return ans;
    }
};