# DP Problems

unknown
java
2 months ago
3.2 kB
60
Indexable
Never
```class DP {
public static int lps_rec(String str, int i, int j){
if(i>j){
return 0;
}

if(i==j){
return 1;
}

int ans = 0;
if(str.charAt(i) == str.charAt(j)){
ans = lps_rec(str, i+1, j-1) + 2;
} else {
ans = Math.max(lps_rec(str, i+1, j), lps_rec(str, i, j-1));
}

return ans;
}

public static int lps_memo(String str, int i, int j, int[][] dp){
if(i>j){
return dp[i][j] = 0;
}

if(i==j){
return dp[i][j] = 1;
}

if(dp[i][j] != 0){
return dp[i][j];
}

int ans = 0;
if(str.charAt(i) == str.charAt(j)){
ans = lps_memo(str, i+1, j-1, dp) + 2;
} else {
ans = Math.max(lps_memo(str, i+1, j, dp), lps_memo(str, i, j-1, dp));
}

return dp[i][j] = ans;
}

public static int lps_tab(String str, int i, int j, int[][] dp){
int n = str.length();
for(int diag = 0; diag<n; diag++){
for(i=0, j=diag; j<n; i++, j++){
if(i==j){
dp[i][j] = 1;
continue;
}

int ans = 0;
if(str.charAt(i) == str.charAt(j)){
ans = dp[i+1][j-1] + 2; //lps_memo(str, i+1, j-1, dp) + 2;
} else {
ans = Math.max(dp[i+1][j], dp[i][j-1]);//Math.max(lps_memo(str, i+1, j, dp), lps_memo(str, i, j-1, dp));
}

dp[i][j] = ans;
}
}

return dp[0][n-1];
}

public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];

return lps_tab(s,0,n-1, dp);
}

public boolean rec(int[] nums, int n, int tar){
if(tar == 0){
return true;
}

if(n==0){
return false;
}

boolean ans = rec(nums, n-1, tar); // no call

if(tar - nums[n-1] >= 0){
ans = ans || rec(nums, n-1, tar-nums[n-1]); // yes call
}

return ans;
}

public boolean rec_memo(int[] nums, int n, int tar, Boolean[][] dp){
if(tar == 0){
return dp[n][tar] = true;
}

if(n==0){
return dp[n][tar] = false;
}

if(dp[n][tar] != null){
return dp[n][tar];
}

boolean ans = rec_memo(nums, n-1, tar, dp); // no call

if(tar - nums[n-1] >= 0){
ans = ans || rec_memo(nums, n-1, tar-nums[n-1], dp); // yes call
}

return dp[n][tar] = ans;
}
public boolean canPartition(int[] nums) {
int n = nums.length;

int sum = 0;
for(int i=0; i<n; i++){
sum += nums[i];
}

if(sum % 2 != 0){
return false;
}

int tar = sum/2;

Boolean[][] dp = new Boolean[n+1][tar+1]; // -1 -> no answer, 0 -> false, 1 -> true

return rec_memo(nums, n, tar, dp);
}
public static void main(String[] args){

}
}```