Dynamic Programming .
Questions Name
Q1 Rod Cutting
Q2 SubSetSum
Q3 Longest Common SubSequence
Q4 Jump Game
Q5 House Robber
Q6 Longest Valid Subsequence
Q7 Unique Paths
Q8 Min Path Sum
Q9 Tapping Rain Water
Q10 Sliding Window Max
Rod Cutting
public class RodCutting {
public static int maxProfit(int[] profit) {
int n= profit.length;
int[] dp= new int[n+1];
for(int i=1;i<=n;i++) {
for(int j =1;j<=i;j++) {
dp[i] = Math.max(dp[i],profit[j-1] + dp[i-j]);
}
}
return dp[n];
public static void main(String[] args) {
int[] profit={3,2,8,9,17,17,20};
System.out.println(maxProfit(profit));
}
SubSetSum
public class SubSetSum {
public static boolean isSubset(int[] nums, int sum) {
int n = nums.length;
boolean[][] dp = new boolean[n+1][sum+1];
for(int i = 0;i<=n;i++) {
dp[i][0] = true;
}
for(int i=1;i<=n;i++) {
for(int j = 1;j<= sum;j++) {
if(j < nums[i-1]){
dp[i][j]= dp[i-1][j];
}
else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][sum];
public static void main(String args[]) {
int[] nums = {3,17,4,5,18,20};
System.out.println(isSubset(nums,12));
}
Longest Common SubSequence (Leetcode ques 1143)
public class LongestCommonSubSeq {
public static int lcs(String s1,String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++) {
for(int j = 1;j<=n;j++) {
if(s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
public static void main(String[] args) {
String x = "ATGCATTGG";
String y = "GTATAGCC";
System.err.println(lcs(x,y));
}
}
Jump Game ( Leet code 55 )
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int far = 0;
for(int i=0;i<n;i++){
if(i>far) {
return false;
far=Math.max(far, i+nums[i]);
if(far>=n-1)
{
return true;
}
}
return false;
}
}
House Robber ( Leet code 198 )
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
dp[1] = nums[0];
for(int i = 2;i<=n;i++) {
dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1]);
}
return dp[n];
}
Longest Valid Subsequence
Unique Paths
Min Path Sum
Tapping Rain Water
Sliding Window Maximum
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] index = new int[n];
int[] result = new int[n+1-k];
int first=0,last=0;
for(int i=0;i<n;i++) {
while(first < last && nums[index[last-1]] <= nums[i]) {
last--;
}
index[last++] = i;
if(index[first] == i-k ) {
first++;
}
if(i >=k -1) {
result[i-k+1] = nums[index[first]];
}
}
return result;
}
}
