0

The link of the question is https://practice.geeksforgeeks.org/problems/longest-palindromic-subsequence/0 . May I know whether my approach is a correct solution using Dynamic Programming . The code is :

#include <bits/stdc++.h>
using namespace std;
int main() {
    //code
    int t;
    cin>>t;
    while(t--){
        string a;
        cin>>a;
        int l = a.length();
        int dp[l][l] = {0};
        for(int i = 0; i<l; i++){
            for(int j = 0; j<l; j++){
                if(i==j){
                    dp[i][i] = 1;
                }
            }
        }
        for(int i = 1; i<l; i++){
            int r = 0;
            int c = i;
            while(r<l and c<l){
                if(a[r]==a[c]){
                    dp[r][c] = dp[r+1][c-1]+2;
                }
                else{
                    dp[r][c] = max(dp[r+1][c], dp[r][c-1]);
                }
                r++;
                c++;
            }
        }
        cout<<dp[0][l-1]<<endl;
    }
    return 0;
}

where t is the number of test cases and a is the input string . We have to determine the length of the longest palindromic subsequence .

Evg
  • 25,259
  • 5
  • 41
  • 83
Krishanu Kashyap
  • 9
  • 2
  • "whether my approach is a correct solution using Dynamic Programming" What makes your doubt that? If you do not know then you probably have tested and not found a problem to discuss here. It seems that you are asking for a review of code you do not see a problem with. – Yunnosch Jan 04 '21 at 12:50
  • 2
    Any site that teaches things like `#include ` and `int l = a.length();` should be banned for good. [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Evg Jan 04 '21 at 12:54

0 Answers0