<p>Given a string <code>s</code>, return <code>true</code> <em>if it is possible to split the string</em> <code>s</code> <em>into three <strong>non-empty</strong> palindromic substrings. Otherwise, return </em><code>false</code>.​​​​​</p>

<p>A string is said to be palindrome if it the same string when reversed.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcbdd&quot;
<strong>Output:</strong> true
<strong>Explanation: </strong>&quot;abcbdd&quot; = &quot;a&quot; + &quot;bcb&quot; + &quot;dd&quot;, and all three substrings are palindromes.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcbddxy&quot;
<strong>Output:</strong> false
<strong>Explanation: </strong>s cannot be split into 3 palindromes.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code>​​​​​​ consists only of lowercase English letters.</li>
</ul>

// class Solution {
// public:
//     bool checkPartitioning(string s) {
        
//     }
// };
class Solution {
public:
int dp[2001][4]={0};

    bool find(string &s,int index,int cnt,vector<vector<int>>&palin){
        if(cnt>3){
            return 0;
        }
        if(index>=s.size()){
            return cnt==3;
        }
        if(dp[index][cnt]!=0){
            return dp[index][cnt]-1;
        }
        for(int i=index;i<s.size();i++){
            if(palin[index][i] && find(s,i+1,cnt+1,palin)){
                dp[index][cnt]=2;
                return 1;
            }
        }
        dp[index][cnt]=1;
        return 0;
    }
    bool checkPartitioning(string s) {

        vector<vector<int>>palin(s.size()+1,vector<int>(s.size()+1,0));
        for(int i=0;i<s.size();i++){
            palin[i][i]=1;
        }
        for(int i=0;i<s.size()-1;i++){
            if(s[i]==s[i+1]){

            palin[i][i+1]=1;
            }
        }
        // for odd len
        for(int i=3;i<=s.size();i+=2){
            int ini=0;
            int end=i-1;
            while(ini>=0 && end<s.size()){
                if(s[ini]==s[end]){
                palin[ini][end]=palin[ini+1][end-1];

                }
                ini++;
                end++;
            }
        }
        // for even len
        for(int i=4;i<=s.size();i+=2){
            int ini=0;
            int end=i-1;
            // if(s[ini]==s[ini+1]){
            //     palin[ini][ini+1]=1;
                
            // }
            while(ini>=0 && end<s.size()){
                if(s[ini]==s[end]){
                palin[ini][end]=palin[ini+1][end-1];

                }
                ini++;
                end++;
            }

        }
        return find(s,0,0,palin);
        
    }
};
119051