516. Longest Palindromic Subsequence

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

Example 1:
Input:

```"bbbab"
```
Output:
```4
```
One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:

```"cbbd"
```
Output:
```2
```
One possible longest palindromic subsequence is "bb".

Constraints:

• `1 <= s.length <= 1000`
• `s` consists only of lowercase English letters.

516. Longest Palindromic Subsequence
``````struct Solution;
use std::i32;

impl Solution {
fn longest_palindrome_subseq(s: String) -> i32 {
let s: Vec<char> = s.chars().collect();
let n = s.len();
let mut dp: Vec<Vec<i32>> = vec![vec![0; n + 1]; n];
for i in 0..n {
dp[i][i + 1] = 1;
}
for w in 2..=n {
for i in 0..=n - w {
let j = i + w;
if s[i] == s[j - 1] {
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
dp[i][j] = i32::max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
dp[0][n]
}
}

#[test]
fn test() {
let s = "bbbab".to_string();
let res = 4;
assert_eq!(Solution::longest_palindrome_subseq(s), res);
let s = "cbbd".to_string();
let res = 2;
assert_eq!(Solution::longest_palindrome_subseq(s), res);
}
``````