class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m,vector<int>(n,INT_MAX));dp[0][0]=grid[0][0];if(m==1 && n==1)return grid[0][0];for(int i=1;i<m;i++) {dp[i][0] = dp[i-1][0]+grid[i][0];}for(int j=1;j<n;j++) {dp[0][j] = dp[0][j-1]+grid[0][j];}for(int i=1;i<m;i++) {for(int j=1;j<n;j++) {dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}return dp[m-1][n-1];}
};
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n));for(int i=0;i<m;i++) dp[i][0] = 1;for(int j=0;j<n;j++) dp[0][j] = 1;for(int i=1;i<m;i++) {for(int j=1;j<n;j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};
class Solution {
public:string longestPalindrome(string s) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size()));string res;int max_length=1;int start = 0;for(int i=0;i<s.size();i++) {for(int j=i;j>=0;j--) {if(i==j)dp[j][i]=1;else if(i==j+1) {dp[j][i]=(s[i]==s[j]);}else {dp[j][i]=(s[i]==s[j])&&dp[j+1][i-1];}if(dp[j][i] && (i-j+1)>max_length) {max_length = i-j+1;start=j;}}}return s.substr(start,max_length);}
};
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int length1 = text1.size();int length2 = text2.size();vector<vector<int>> dp(length1+1, vector<int>(length2+1,0));int res = 0;for(int i=1;i<=length1;i++) {for(int j=1;j<=length2;j++) {if(text1[i-1] != text2[j-1]) {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}else {dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]);}res = max(res,dp[i][j]);}}return res;}
};
