Blog · Jul 22, 2025
Dynamic Programming patterns every software engineer should know
Dynamic Programming patterns every software engineer should know
DP for Beginners [Problems | Patterns | Sample Solutions]
https://leetcode.com/discuss/general-discussion/662866/dp-for-beginners-problems-patterns-sample-solutions
As some folks requested to list down good Dynamic Programming problems to start practice with. So, I am listing down them below and dividing them into different DP problem pattern. Problem listed in group follow a particular pattern and similar approach to solve them. I have tried to list those which till now I have solved, might have missed a few as well. Mostly are LC Medium problems and few LC Hard ones.
Beginner folks can wish to look at solutions listed below of particular pattern and can try to solve the other problem themselves.
Full problem list: https://leetcode.com/list/x1k8lxi5
KnapSack Dp
[https://leetcode.com/problems/shopping-offers/description/] (https://leetcode.com/problems/shopping-offers/description/)
Longest Increasing Subsequence variants:
https://leetcode.com/problems/longest-increasing-subsequence/
https://leetcode.com/problems/largest-divisible-subset/
https://leetcode.com/problems/russian-doll-envelopes/
https://leetcode.com/problems/maximum-length-of-pair-chain/
https://leetcode.com/problems/number-of-longest-increasing-subsequence/
https://leetcode.com/problems/delete-and-earn/
https://leetcode.com/problems/longest-string-chain/
Partition Subset:
https://leetcode.com/problems/partition-equal-subset-sum/
https://leetcode.com/problems/last-stone-weight-ii/
BitMasking:
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
Longest Common Subsequence Variant:
https://leetcode.com/problems/longest-common-subsequence/
https://leetcode.com/problems/edit-distance/
https://leetcode.com/problems/distinct-subsequences/
https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
Palindrome:
https://leetcode.com/problems/palindrome-partitioning-ii/
https://leetcode.com/problems/palindromic-substrings/
Coin Change variant:
https://leetcode.com/problems/coin-change/
https://leetcode.com/problems/coin-change-2/
https://leetcode.com/problems/combination-sum-iv/
https://leetcode.com/problems/perfect-squares/
https://leetcode.com/problems/minimum-cost-for-tickets/
Matrix multiplication variant:
https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
https://leetcode.com/problems/burst-balloons/
Matrix/2D Array:
https://leetcode.com/problems/matrix-block-sum/
https://leetcode.com/problems/range-sum-query-2d-immutable/
https://leetcode.com/problems/dungeon-game/
https://leetcode.com/problems/triangle/
https://leetcode.com/problems/maximal-square/
https://leetcode.com/problems/minimum-falling-path-sum/
Hash + DP:
https://leetcode.com/problems/target-sum/
https://leetcode.com/problems/longest-arithmetic-sequence/
https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
State machine:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
Depth First Search + DP:
https://leetcode.com/problems/out-of-boundary-paths/
https://leetcode.com/problems/knight-probability-in-chessboard/
Minimax DP:
https://leetcode.com/problems/predict-the-winner/
https://leetcode.com/problems/stone-game/
Misc:
https://leetcode.com/problems/greatest-sum-divisible-by-three/
https://leetcode.com/problems/decode-ways/
https://leetcode.com/problems/perfect-squares/
https://leetcode.com/problems/count-numbers-with-unique-digits/
https://leetcode.com/problems/longest-turbulent-subarray/
https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
Sample solutions for each of above problem type:
KnapSack dp https://leetcode.com/list/o02bxeuh [https://leetcode.com/problems/shopping-offers/description/] (https://leetcode.com/problems/shopping-offers/description/) [https://leetcode.com/problems/house-robber-ii/?envType=list&envId=o02bxeuh] [https://leetcode.com/problems/ones-and-zeroes/?envType=list&envId=o02bxeuh] [https://leetcode.com/problems/shopping-offers/?envType=list&envId=o02bxeuh] [https://leetcode.com/problems/target-sum/?envType=list&envId=o02bxeuh]
Shoppong Offers [https://leetcode.com/problems/shopping-offers/description/] (https://leetcode.com/problems/shopping-offers/description/)
class Solution {
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
HashMap<List<Integer> ,Integer> dp = new HashMap<>();
return offers(price,special,needs,dp);
}
int offers(List<Integer> price, List<List<Integer>> special, List<Integer> need , HashMap<List<Integer> ,Integer> dp){
if(dp.containsKey(need)){
return dp.get(need);
}
// not to take any special offer
int nos = 0;
for(int i=0 ; i<need.size() ; i++){
nos +=(need.get(i)*price.get(i));
}
// take any special offer and call recursion function on remaining needs
int min=Integer.MAX_VALUE;
for(int i=0 ; i<special.size(); i++){
List<Integer> sp = special.get(i);
// check if no item is taken more than need
if(cantake(sp,need)){
for(int k=0 ; k<need.size() ; k++){
need.set(k,need.get(k)-sp.get(k));
}
int a = offers(price,special,need,dp) + sp.get(sp.size()-1);
min = Math.min(min,a);
for(int k=0 ; k<need.size() ; k++){
need.set(k,need.get(k)+sp.get(k));
}
}
}
int ans = Math.min(min,nos);
dp.put(need,ans);
return ans;
}
boolean cantake(List<Integer> sp , List<Integer> nd){
for(int i=0 ; i<nd.size() ; i++){
if(nd.get(i)-sp.get(i)<0){
return false;
}
}
return true;
}
}
## House Robbers [https://leetcode.com/problems/house-robber-ii/](https://leetcode.com/problems/house-robber-ii)
```java
class Solution {
int dp[][];
public int rob(int[] nums) {
if(nums.length == 1)return nums[0];
dp = new int[nums.length+1][2];
for(int i[] : dp)Arrays.fill(i,-1);
int one = helper(nums,0,nums.length-2,0);
int two = helper(nums,1,nums.length-1,1);
return Math.max(one,two);
}
public int helper(int nums[],int start,int n,int idx){
if(n < start)return 0;
if(n == start)return dp[n][idx] = nums[start];
if(dp[n][idx] != -1)return dp[n][idx];
return dp[n][idx] = Math.max(helper(nums,start,n-1,idx),helper(nums,start,n-2,idx) + nums[n]);
}
}
### Target Sum[https://leetcode.com/problems/target-sum/](https://leetcode.com/problems/target-sum/)
```java
class Solution {
int answer=0;
public int findTargetSumWays(int[] nums, int target) {
recur(nums,target,0);
return answer;
}
public void recur(int[] nums,int target,int i){
if(i>=nums.length &&0==target){
answer++;
return;
}else if(i>=nums.length){return;}
recur(nums,target+(nums[i]*(-1)),i+1);
recur(nums,target+(nums[i]),i+1);
}
}
Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/
https://leetcode.com/problems/largest-divisible-subset/
https://leetcode.com/problems/russian-doll-envelopes/
https://leetcode.com/problems/maximum-length-of-pair-chain/
https://leetcode.com/problems/number-of-longest-increasing-subsequence/
https://leetcode.com/problems/delete-and-earn/
https://leetcode.com/problems/longest-string-chain/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int>LIS(n+1, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
LIS[i] = max(LIS[i], 1 + LIS[j]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, LIS[i]);
}
return ans;
}
};
Partition Subset Sum:
https://leetcode.com/problems/partition-equal-subset-sum/
https://leetcode.com/problems/last-stone-weight-ii/
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (int i = 0; i < n; i++)
sum += nums[i];
if (sum % 2 != 0) return false;
int target = sum/2;
vector<bool>dp(target+1, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = dp[j] | dp[j - nums[i]];
}
}
return dp[target];
}
};
BitMasking in DP:
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
class Solution {
int dp[(1<<16) + 2];
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int n = nums.size();
fill(dp, dp+(1<<16)+2, -1);
int sum = 0;
for (int i = 0; i < n; i++)
sum += nums[i];
if (sum % k != 0) return false;
int target = sum/k;
dp[0] = 0;
for (int mask = 0; mask < (1<<n); mask++) {
if (dp[mask] == -1) continue;
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i)) && dp[mask] + nums[i] <= target)
dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target;
}
}
return dp[(1<<n)-1] == 0;
}
};
Longest Common Subsequence
https://leetcode.com/problems/longest-common-subsequence/
https://leetcode.com/problems/edit-distance/
https://leetcode.com/problems/distinct-subsequences/
https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
class Solution {
int[][] dp=null;
public int longestCommonSubsequence(String text1, String text2) {
dp = new int[text1.length() + 1][text2.length() + 1];
for(int arr[] : dp) Arrays.fill(arr, -1);
return recur(0,0,text1,text2);
}
public int recur(int t1,int t2,String text1,String text2){
if(t1>=text1.length()||t2>=text2.length())return 0;
if(dp[t1][t2]!=-1)return dp[t1][t2];
if(text1.charAt(t1)==text2.charAt(t2)){
return dp[t1][t2]=1+recur(t1+1,t2+1,text1,text2);
}
return dp[t1][t2]=Math.max(recur(t1+1,t2,text1,text2),recur(t1,t2+1,text1,text2));
}
}
class Solution {
int longestCommonSubsequenceUtil(string text1, string text2, int n, int m) {
if (n == 0 || m == 0)
return 0;
vector<vector<int>>L(n+1, vector<int>(m+1, 0));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (text1[i-1] == text2[j-1])
L[i][j] = 1 + L[i-1][j-1];
else
L[i][j] = max(L[i][j-1], L[i-1][j]);
}
}
return L[n][m];
}
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
return longestCommonSubsequenceUtil(text1, text2, n, m);
}
};
Palindrome:
https://leetcode.com/problems/palindrome-partitioning-ii/
https://leetcode.com/problems/palindromic-substrings/
Palindrome partition Code
class Solution {
public int minCut(String s) {
int n=s.length();
int[] dp=new int[n+1];
Arrays.fill(dp,-1);
if(isPalin(s,0,n-1))return 0;
return recur(0,s,dp,n)-1;
}
public int recur(int i,String s,int[] dp,int n){
if(i==n)return 0;
if(dp[i]!=-1)return dp[i];
int minC = Integer.MAX_VALUE;
int c=0;
for(int k=i;k<n;k++){
if(isPalin(s,i,k)){
c=1+recur(k+1,s,dp,n);
// System.out.println(" k "+k+" c "+c);
minC=Math.min(minC,c);
}
}
return dp[i]=minC;
}
public boolean isPalin(String s,int i,int j){
if(i>j)return false;
while(i<j){
if(s.charAt(i)!=s.charAt(j))
{ return false;
}
i++;
j--;
}
return true;
}
}
Second approach simple intuitive but TLE
```java class Solution { int min=Integer.MAX_VALUE; int[] dp=null; public int minCut(String s) { dp=new int[s.length()]; Arrays.fill(dp,Integer.MAX_VALUE); recur(0,0,s,0); Arrays.stream(dp).forEach(x->System.out.print(“ “+x)); return dp[dp.length-1]; } public void recur(int i,int j,String s,int count){ if(i>s.length()||j>s.length()){ min=Math.min(min,count); // System.out.println(count); return; } String current=s.substring(i,j); if(current.equals(new StringBuilder(current).reverse().toString())) { dp[i]=Math.min(dp[i],count); System.out.println(“ i “+i+” j “+j+” C “+current+” dp[i] “+dp[i]); recur(j,j+1,s,count+1); recur(i,j+1,s,count); } //start from count 0 because charecter dont match recur(i,j+1,s,0);
} }
#### Third approach tabulation
```java class Solution{
public int minCut(String s) {
int n,min;
n = s.length();
//cut[i] represents minimum number of cuts from String 0 to i
int[] cut = new int[n];
//p[i][j] represents String i to j is a palindrome or not
boolean[][] p = new boolean[n][n];
for(int i=0;i<n;i++)
{
min = i; // Max number of cuts is i for string length i+1
for(int j=0;j<=i;j++)
{
// Why i - j < 3 ?
// 1. String of length 1 is always palindrome so no need to check in boolean table
// 2. String of length 2 is palindrome if Ci == Cj which is already checked in first part so no need to check again
// 3. String of length 3 is palindrome if Ci == Cj which is already checked in first part and Ci+1 and Cj-1 is same character which is always a palindrome
// If String length >=4
// then check if Ci == Cj and if they are equal check if String[j+1 .. i-1] is a palindrome from the boolean table
if(s.charAt(j) == s.charAt(i) && (i-j < 3 || p[j+1][i-1]))
{
// Its a palindrome as Ci == Cj and String[j+1...i-1] is a palindrome
p[j][i] = true;
// j == 0 because String from j to i is a palindrome and it starts from first character so means no cuts needed
// Else I need a cut at jth location and it will be cuts encountered till j-1 + 1
min = j == 0 ? 0 : Math.min(min, cut[j-1] + 1);
}
}
cut[i]=min;
}
return cut[n-1];
}
class Solution {
public:
int minCut(string s) {
int n = s.length();
int res[n];
bool P[n][n];
for (int i = 0; i < n; i++)
P[i][i] = true;
for (int L = 2; L <= n; L++) {
for (int i = 0; i < n-L+1; i++) {
int j = i+L-1;
if (L == 2) {
P[i][j] = (s[i] == s[j]);
} else {
P[i][j] = (s[i] == s[j]) && P[i+1][j-1];
}
}
}
for (int i = 0; i < n; i++) {
if (P[0][i])
res[i] = 0;
else {
res[i] = INT_MAX;
for (int j = 0; j < i; j++) {
if (P[j+1][i] && res[i] > 1 + res[j])
res[i] = 1+res[j];
}
}
}
return res[n-1] == INT_MAX ? 1 : res[n-1];
}
};
**Coin Change:**
[https://leetcode.com/problems/coin-change/](https://leetcode.com/problems/coin-change/)
[https://leetcode.com/problems/coin-change-2/](https://leetcode.com/problems/coin-change-2/)
[https://leetcode.com/problems/combination-sum-iv/](https://leetcode.com/problems/combination-sum-iv/)
[https://leetcode.com/problems/perfect-squares/](https://leetcode.com/problems/perfect-squares/)
[https://leetcode.com/problems/minimum-cost-for-tickets/](https://leetcode.com/problems/minimum-cost-for-tickets/)
My Solution Coin Change
class Solution {
int[] dp=null;
public int coinChange(int[] coins, int amount) {
dp=new int[amount+1];
Arrays.fill(dp,-1);
int result= r(coins,amount);
if(result==Integer.MAX_VALUE){
return -1;
}
return result;
}
public int r(int[] coins,int amount){
if(amount==0)
{ //System.out.println(" amt "+amount);
return 0;
}
if(amount<0){
// System.out.println(" amt "+amount);
return Integer.MAX_VALUE; //because we want to increase so that it wont be added in the result
}
if(dp[amount]!=-1)return dp[amount];
int minCoins = Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++){
//if(coins[i]>amount)continue;
int ans=r(coins,amount-coins[i]);
if(ans!=Integer.MAX_VALUE){
minCoins=Math.min(minCoins,ans+1);//due to this min() the value Integer.MAX returned by <0 will be ommitted
}
}
return dp[amount]=minCoins;
}
// public void r(int [] coins,int amount,int coin,int start){
// if(amount==0){
// mxCoins=Math.min(mxCoins,coin);
// return;
// }
// if(amount<0)return;
// if(dp[start]!=Integer.MAX_VALUE)return;
// for(int i=start;i<coins.length;i++){
// if(coins[i]>amount)continue;
// dp[i]=Math.min(dp[i],amount-coins[i]);
// r(coins,amount-coins[i],coin+1,0);
// }
// }
}
```c++ class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
if (n == 0) return 0;
vector<int>res(amount+1, INT_MAX);
res[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
if (res[j-coins[i]] != INT_MAX)
res[j] = min(res[j], 1+res[j-coins[i]]);
}
}
return res[amount] != INT_MAX ? res[amount] : -1;
}
};
Matrix multiplication:
https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
https://leetcode.com/problems/burst-balloons/
https://leetcode.com/problems/burst-balloons/solutions/892552/for-those-who-are-not-able-to-understand-any-solution-with-diagram/
***Minimum cost tree from leaf values
1130. Minimum Cost Tree From Leaf Values
Minimum cost tree from leaf values 1130. Minimum Cost Tree From Leaf Values
```java class Solution {
int[] dp=null;
public int mctFromLeafValues(int[] arr) {
int dp[][] = new int[arr.length+1][arr.length+1];
for(int i=0;i<=arr.length;++i)
{
for(int j = 0; j<=arr.length;++j)
{
dp[i][j] = -1;
}
}
return recur(arr,0,arr.length-1,dp);
}
public int mxNum(int[] arr,int l,int r){
int min=arr[l];
//preincrement because we always want minimum to start from 1
for(int i=l;i<=r;++i){
min=Math.max(arr[i],min);
}
return min;
}
public int recur(int[] arr,int i,int j,int[][] dp){ if(i>=j)return 0; int ans=Integer.MAX_VALUE; if(dp[i][j]!=-1)return dp[i][j];
//preincrement ++k because we always want minimum to start from 1
for(int k=i;k<j;++k){
ans=Math.min(mxNum(arr,i,k)*mxNum(arr,k+1,j)
+
recur(arr,i,k,dp)
+
recur(arr,k+1,j,dp), ans);
}
return dp[i][j]=ans; } }
class Solution {
public:
int minScoreTriangulation(vector
int n = A.size();
vector<vector<int>>dp(n, vector<int>(n, 0));
for (int L = 2; L <= n; L++) {
for (int i = 0; i+L < n; i++) {
int j = i+L;
dp[i][j] = INT_MAX;
for (int k = i+1; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]);
}
}
}
return dp[0][n-1];
} }; ```
Matrix/2D Array:
https://leetcode.com/problems/matrix-block-sum/
https://leetcode.com/problems/range-sum-query-2d-immutable/
https://leetcode.com/problems/dungeon-game/
https://leetcode.com/problems/triangle/
https://leetcode.com/problems/maximal-square/
https://leetcode.com/problems/minimum-falling-path-sum/
https://leetcode.com/problems/matrix-block-sum/
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>>sum(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
}
}
vector<vector<int>>res(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int r1 = max(0, i-K); int c1 = max(0, j-K);
int r2 = min(m-1, i+K); int c2 = min(n-1, j+K);
r1++; r2++;
c1++; c2++;
res[i][j] = sum[r2][c2] - (sum[r2][c1-1] + sum[r1-1][c2]- sum[r1-1][c1-1]);
}
}
return res;
}
};
Hash + DP:
https://leetcode.com/problems/target-sum/
https://leetcode.com/problems/longest-arithmetic-sequence/
https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
https://leetcode.com/problems/target-sum/
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size();
unordered_map<int, int>hm;
hm[0] = 1;
for (int i = 0; i < n; i++) {
auto mp = hm;
hm.clear();
for (auto it = mp.begin(); it != mp.end(); it++) {
hm[it->first + nums[i]] += it->second;
hm[it->first - nums[i]] += it->second;
}
}
return hm[S];
}
};
State machine:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<int>buy(n, 0);
vector<int>sell(n, 0);
buy[0] = -prices[0], sell[0] = 0;
for (int i = 1; i < n; i++) {
buy[i] = max(buy[i-1], sell[i-1]-prices[i]);
sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee);
}
return sell[n-1];
}
};
Depth First Search +DP:
https://leetcode.com/problems/out-of-boundary-paths/
https://leetcode.com/problems/knight-probability-in-chessboard/
class Solution {
int mod = 1000000007;
int dfs(int m, int n, int N, int r, int c, vector<vector<vector<int>>>& dp) {
if (r < 0 || c < 0 || r >= m || c >= n) return 1;
if (N == 0) return 0;
if (dp[N][r][c] != -1) return dp[N][r][c]%mod;
int moves = 0;
moves = (moves + dfs(m, n, N-1, r, c+1, dp))%mod;
moves = (moves + dfs(m, n, N-1, r, c-1, dp))%mod;
moves = (moves + dfs(m, n, N-1, r+1, c, dp))%mod;
moves = (moves + dfs(m, n, N-1, r-1, c, dp))%mod;
dp[N][r][c] = moves%mod;
return dp[N][r][c];
}
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector<int>>>dp(N+1, vector<vector<int>>(m+1, vector<int>(n+1, -1)));
return dfs(m, n, N, i, j, dp);
}
};
Minimax DP:
https://leetcode.com/problems/predict-the-winner/
https://leetcode.com/problems/stone-game/
Coin Change 2
class Solution {
int[][] dp=null;
public int change(int amount, int[] coins) {
dp=new int[coins.length][amount+1];
for(int[] r:dp){
Arrays.fill(r,-1);
}
int answer=recur(coins,amount,0);
return answer;
}
public int recur(int[] coins,int amount,int i){
if (amount == 0 ) return 1;
if (amount < 0 ) return 0;
int w=0;
if (i==coins.length)return 0;
if (dp[i][amount]!=-1)return dp[i][amount];
//if coin is bigger simply move forward
if ( coins[i] > amount ) {
return recur(coins,amount,i+1);
}
//decision whether include coin or not
int ans= recur(coins,amount-coins[i],i);
int not= recur(coins,amount,i+1);
w = ans + not;
dp[i][amount]=w;
return w;
}
}
Predict winner
editorial selected answer with comments
```java class Solution {
int[][] memo;
private int maxDiff(int[] nums, int left, int right, int n) {
if (memo[left][right] != -1) {
return memo[left][right];
}
if (left == right) {
return nums[left];
}
System.out.println("L "+left);
//this negative simulates the alternative player2s turn because -(-) becomes postive and in next -(+) becomes negative this way we simulate another players sum
int scoreByLeft = nums[left] - maxDiff(nums, left + 1, right, n);
int scoreByRight = nums[right] - maxDiff(nums, left, right - 1, n);
memo[left][right] = Math.max(scoreByLeft, scoreByRight);
return memo[left][right];
}
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
memo = new int[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(memo[i], -1);
}
return maxDiff(nums, 0, n - 1, n) >= 0;
}
}
default answer
class Solution {
public:
bool PredictTheWinner(vector
int res[n][n];
for (int i = 0; i < n; i++)
res[i][i] = nums[i];
for (int l = 2; l <= n; l++) {
for (int i = 0; i+l-1 < n; i++) {
int j = i+l-1;
int a = (i+1 <= j-1) ? res[i+1][j-1] : 0;
int b = (i+2 <= j) ? res[i+2][j] : 0;
int c = (i <= j-2) ? res[i][j-2] : 0;
res[i][j] = max(nums[i] + min(a,b), nums[j] + min(a, c));
}
}
int total = 0;
for (int i = 0; i < n; i++)
total += nums[i];
return res[0][n-1] >= total - res[0][n-1];
} }; ```
Miscellaneous:
https://leetcode.com/problems/greatest-sum-divisible-by-three/
https://leetcode.com/problems/decode-ways/
https://leetcode.com/problems/count-numbers-with-unique-digits/
https://leetcode.com/problems/longest-turbulent-subarray/
https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
Please point out issues in solutions if you find any. There might be better approaches in few.
Link Credit: https://leetcode.com/discuss/general-discussion/651719/how-to-solve-dp-string-template-and-4-steps-to-be-followed
I have been doing DP problem on strings for a while and found a pattern / template to solve it, thought of sharing it with you.
Templates for solving it. It was provided by @aatalyk in one of his great article. You can find it here.
1. If you have two strings.
/* Pre-processing. Define basic cases. */
for( int i = 1; i <= m; i++){
for( int j = 1; j <= n; j++){
if(s1[i - 1] == s2[j - 1]){
/* Your code */
}
else{
/* Your code */
}
}
}
2. If you are given only one string
/* Pre-processing. Define basic cases. */
for( int len = 1; len < n; len++){
for( int i = 0; i + len < n; i++){
int j = i + len;
if(s1[i - 1] == s1[j - 1]){
/* Your code */
}
else{
/* Your code */
}
}
}
Problem 1: Edit Distance
Step 1: Read the problem and try to understand it (Hardest Part)
Let’s take this problem and find out what it says!
- Two strings will be provided to you (Ex. horse and ros).
- You can make 3 operations (Insert, Delete, Replace).
- We have to find the minimum no. of operations to convert string1 to string2.
Example: horse and ros
Answer: 3 (You can find it how in the question.)
Step 2: Pre Processing (Tabulation & Define Base Cases)
We have to tabulate the answers for subproblems in order to use it again.
What is a cell in table means? dp[i,j] has the answer for the subproblem string1(:i) and string2(:j)
Define Base Cases. It varies from problem to problem.
In this problem the base cases are,
- What if the string1 and string2 are empty?
- What if the string1 is empty and string2 is not empty and vice versa?
Lets find it out.
- Both String1 and String2 are empty: Then the answer to the subproblem is 0. Since minimum operations to be performed to make string1 as string2 is 0.
- String1 is empty and String2 is not empty: We need insert characters to make it as string2. Minimum operations to be performed will be equal to string2 length.
- String1 is not empty and String2 is empty: We have delete characters to make it as string2.
Step 3:
The main problem definition goes here.
- If both the string have same character we don’t have do any operations, So that min no of operations to be performed is equal to subproblem with state (i - 1, j - 1).
- If characters are different, we can do three operations (Insert, Delete, Replace) We can find minimum between subproblems with states( dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j] ) + 1.
Why these states?
- dp[i - 1][j - 1] => If we replace the character.
- dp[i][j - 1] => If we delete the character.
- dp[i - 1][j] => If we insert the character.
Return dp[string1.length][string2.length]. Since it contains the answer for subproblem between two strings.
Here is my C++ Code. Status: Accepted.
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));
for(int i = 1; i <= n; i++){
dp[i][0] = 1 + dp[i - 1][0];
}
for(int i = 1; i <= m; i++){
dp[0][i] = 1 + dp[0][i - 1];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(word2[i - 1] == word1[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
}
}
}
return dp[n][m];
}
Problem 2: Delete Operations for Two Strings
STEP 1: Understand the problem.
Quick explanation: We can delete a character in either string in each move to make both string equal. Return minimum no. of moves.
STEP 2: Base Cases
- Both strings are empty: 0
- One string is empty. We have to delete all the character in other string to make it empty. So min. no of moves has to be equal to the length of the non-empty string.
STEP 3: Definition of problem.
- If both characters are same. We dont have to delete it, so the moves will be equal to subproblem with state(i -1, j - 1)
- If both characters are not the same. We can delete character from either string. So the min no of moves has to be minimum between dp[i][j - 1] and dp[i - 1][j].
Code:
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
for(int i = 1; i <= m; i++){
dp[i][0] = 1 + dp[i - 1][0];
}
for(int i = 1; i <= n; i++){
dp[0][i] = 1 + dp[0][i - 1];
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
.
Problem 3: Minimum ASCII Delete Sum for two Strings
Similar to problem 2. One change here we store ASCII values instead of count of moves.
int minimumDeleteSum(string s1, string s2) {
int m = s1.length();
int n = s2.length();
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
for(int i = 1; i <= m; i++){
dp[i][0] = dp[i - 1][0] + s1[i - 1];
}
for(int j = 1; j <= n; j++){
dp[0][j] = dp[0][j - 1] + s2[j - 1];
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s1[i - 1] == s2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min((int) s1[i - 1] + dp[i -1][j], (int)s2[j - 1] + dp[i][j - 1]);
}
}
}
return dp[m][n];
}
.
Problem 4: Longest Palindromic Subsequence
STEP 1: Understand the question.
Return length of the longest palindrome subsequence.
STEP 2: Base Cases
Every single character is a palindrome.
What does a cell in the table or vector means? Maximum length of palindrome that exists between i and j.
STEP 3: Main definition.
It varies since single string is given. The code looks like interval dp problems.
- What if two characters are matching? we have return 2 + dp[i + 1][j - 1].
Why? 2 for the two characters & then find for the interval i + 1 and j - 1. - What if two characters are not matching? We have find maximum between two subproblems (dp[i + 1][j] and dp[i][j - 1] )
- ```java class Solution {
int[][]dp=null;
public int longestPalindromeSubseq(String s) {
int result=0;
for(int i=0;i<s.length();i++){
dp=new int[s.length()+1][s.length()+1];
for(int[] d:dp){
Arrays.fill(d,-1);
}
int l=recur(i,i,s);
dp=new int[s.length()+1][s.length()+1];
for(int[] d:dp){
Arrays.fill(d,-1);
}
int r=recur(i,i+1,s);
result=Math.max(result,Math.max(l,r));
}
return result;
}
public int recur(int i,int j,String s){
if(i<0)return 0;
if(j>=s.length())return 0;
if(dp[i][j]!=-1)return dp[i][j];
int in=0;
//for string=bab i=0,j=2
if(s.charAt(i)==s.charAt(j) && i!=j){
in= 2+recur(i-1,j+1,s);
}
//for string=b i=0,j=0
if(s.charAt(i)==s.charAt(j) && i==j){
in+= 1+recur(i-1,j+1,s);
}
// System.out.println(“in “+in+” i “+i+” j “+j);
int ex= Math.max(recur(i-1,j,s),recur(i,j+1,s));
return dp[i][j]=Math.max(in,ex);
}
}
_Code._
int longestPalindromeSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
dp[i][i] = 1;
}
int count = 1;
for(int len = 1; len < n; len++){
for(int i = 0; i + len < n; i++){
int j = i + len;
if(s[i] == s[j]){
dp[i][j] = 2 + dp[i + 1][j - 1];
}
else{
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1]; ```
.
Problem 5: Palindromic Substrings
STEP 1: Understand Question
Count the number of palindrome substrings within a given string.
STEP 2: Base Cases
- Every Single Character is a Palindrome. So start the count as the length of the string.
- Check Adjacent. If the adjacent char is same we can increase the counter.
STEP 3: Main Definition
Template 2, Since single string is given.
One case => Find different i and j combinations. If the character i and j is matching, then we have to find whether i + 1 and j - 1 is matching or not. If matches, we can increase the count and mark it as a palindorme.
Code:
int countSubstrings(string s) {
int n = s.length();
if(n < 2){
return n;
}
vector<vector<int>> dp(n + 1, vector<int> (n + 1, 0));
for(int i = 1; i <= n; i++){
dp[i][i] = 1;
}
int count = n;
for(int i = 0; i < n; i++){
if(s[i] == s[i + 1]) {
count++;
dp[i][i + 1] = 1;
}
}
for(int len = 1; len < n; len++){
for(int i = 0; i + len < n; i++){
int j = len + i;
if(s[i] == s[j] && dp[i + 1][j - 1]){
count++;
dp[i][j] = 1;
}
}
}
return count;
}