Longest Palindrome Subsequence - Dynamic Porgramming

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.

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.DP
{
 public class LongestPalindromeSubseqSoln
 {
 Dictionary<string, int> map = new Dictionary<string, int>();
 public int LongestPalindromeSubseq(string s)
 { 
 return LongestPalindromeSubseqRecursion(s, 0, s.Length-1);
 }

 private int LongestPalindromeSubseqRecursion(string s, int start, int end)
 {
 if (map.ContainsKey(GetKey(start, end))){
 return map[GetKey(start, end)];
 }

 if(start == end)
 {
 return 1;
 }

 if (s[start] == s[end])
 {
 if(start + 1 == end)
 {
 return 2;
 }

 var res = 2 + LongestPalindromeSubseqRecursion(s, start + 1, end - 1);
 map.Add(GetKey(start, end), res);
 return res;
 }
 else
 {
 var res = Math.Max(
 LongestPalindromeSubseqRecursion(s, start+1, end),
 LongestPalindromeSubseqRecursion(s,start,end-1)
 );
 map.Add(GetKey(start, end), res);
 return res;
 }
 }

 private string GetKey(int start, int end)
 {
 return $"{start}-{end}";
 }
 }
}