Contents
1D DP (knapsack/linear)
int knap01(vector<int>& wt, vector<int>& val, int W){
vector<int> dp(W+1, 0);
for (int i=0;i<(int)wt.size();++i)
for (int w=W; w>=wt[i]; --w)
dp[w] = max(dp[w], dp[w-wt[i]] + val[i]);
return dp[W];
}
2D DP (grid/path)
int uniquePaths(vector<vector<int>>& g){
int m=g.size(), n=g[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
if (g[0][0]==1) return 0; dp[0][0]=1;
for (int i=0;i<m;++i) for(int j=0;j<n;++j){
if (g[i][j]==1){ dp[i][j]=0; continue; }
if (i) dp[i][j]+=dp[i-1][j];
if (j) dp[i][j]+=dp[i][j-1];
}
return dp[m-1][n-1];
}
LIS (Longest Increasing Subsequence)
Find the longest subsequence where elements are in strictly increasing order.
Template: O(n²) DP
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
Template: O(n log n) with Binary Search
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}
Count Number of LIS
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> length(n, 1), count(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[j] + 1 == length[i]) {
count[i] += count[j];
}
}
}
}
int maxLen = *max_element(length.begin(), length.end());
int result = 0;
for (int i = 0; i < n; i++) {
if (length[i] == maxLen) {
result += count[i];
}
}
return result;
}
| ID |
Title |
Link |
Solution |
| 300 |
Longest Increasing Subsequence |
Link |
Solution |
| 673 |
Number of Longest Increasing Subsequence |
Link |
Solution |
| 354 |
Russian Doll Envelopes |
Link |
- |
| 334 |
Increasing Triplet Subsequence |
Link |
- |
Interval DP
DP on intervals - solve subproblems for all intervals of length len, then combine.
Template
int intervalDP(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// Base case: length 1
for (int i = 0; i < n; i++) {
dp[i][i] = arr[i]; // or base value
}
// Length 2 to n
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
// Try all splits
for (int k = i; k < j; k++) {
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, k, j));
}
}
}
return dp[0][n-1];
}
Example: Burst Balloons
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> arr = {1};
arr.insert(arr.end(), nums.begin(), nums.end());
arr.push_back(1);
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = max(dp[i][j],
dp[i][k-1] + dp[k+1][j] +
arr[i-1] * arr[k] * arr[j+1]);
}
}
}
return dp[1][n];
}
| ID |
Title |
Link |
Solution |
| 312 |
Burst Balloons |
Link |
- |
| 516 |
Longest Palindromic Subsequence |
Link |
- |
| 1039 |
Minimum Score Triangulation of Polygon |
Link |
- |
| 1130 |
Minimum Cost Tree From Leaf Values |
Link |
- |
State Machine DP
DP where state transitions follow a state machine pattern.
Template: Buy/Sell Stock Pattern
int maxProfit(vector<int>& prices) {
int n = prices.size();
// dp[i][0] = holding stock, dp[i][1] = not holding stock
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = -prices[0]; // Buy on day 0
dp[0][1] = 0; // Don't buy on day 0
for (int i = 1; i < n; i++) {
// Hold: max(keep holding, buy today)
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
// Not hold: max(keep not holding, sell today)
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[n-1][1];
}
Template: Multiple States
int maxProfit(vector<int>& prices) {
int n = prices.size();
// States: rest, hold, sold (cooldown)
vector<vector<int>> dp(n, vector<int>(3, 0));
dp[0][0] = 0; // rest
dp[0][1] = -prices[0]; // hold
dp[0][2] = INT_MIN; // sold
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][2]); // rest from rest or cooldown
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); // hold from hold or buy
dp[i][2] = dp[i-1][1] + prices[i]; // sell
}
return max(dp[n-1][0], dp[n-1][2]);
}
| ID |
Title |
Link |
Solution |
| 121 |
Best Time to Buy and Sell Stock |
Link |
- |
| 122 |
Best Time to Buy and Sell Stock II |
Link |
- |
| 123 |
Best Time to Buy and Sell Stock III |
Link |
- |
| 188 |
Best Time to Buy and Sell Stock IV |
Link |
- |
| 309 |
Best Time to Buy and Sell Stock with Cooldown |
Link |
- |
| 714 |
Best Time to Buy and Sell Stock with Transaction Fee |
Link |
- |
DP on Trees
DP where subproblems are solved on subtrees.
Template: Tree DP
pair<int, int> dfs(TreeNode* root) {
if (!root) return {0, 0};
auto left = dfs(root->left);
auto right = dfs(root->right);
// dp[0] = not take current, dp[1] = take current
int notTake = max(left.first, left.second) +
max(right.first, right.second);
int take = root->val + left.first + right.first;
return {notTake, take};
}
int rob(TreeNode* root) {
auto result = dfs(root);
return max(result.first, result.second);
}
Template: Path Problems
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
function<int(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) return 0;
int left = max(0, dfs(node->left));
int right = max(0, dfs(node->right));
// Path through current node
maxSum = max(maxSum, node->val + left + right);
// Return max path ending at current node
return node->val + max(left, right);
};
dfs(root);
return maxSum;
}
| ID |
Title |
Link |
Solution |
| 337 |
House Robber III |
Link |
- |
| 124 |
Binary Tree Maximum Path Sum |
Link |
- |
| 968 |
Binary Tree Cameras |
Link |
- |
DP with Binary Search
Combine DP with binary search for optimization.
Template: LIS with Binary Search
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}
Template: DP + Binary Search on Answer
int splitArray(vector<int>& nums, int m) {
int left = *max_element(nums.begin(), nums.end());
int right = accumulate(nums.begin(), nums.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
bool canSplit(vector<int>& nums, int m, int maxSum) {
int count = 1, sum = 0;
for (int num : nums) {
if (sum + num > maxSum) {
count++;
sum = num;
} else {
sum += num;
}
}
return count <= m;
}
| ID |
Title |
Link |
Solution |
| 300 |
Longest Increasing Subsequence |
Link |
Solution |
| 410 |
Split Array Largest Sum |
Link |
- |
| 875 |
Koko Eating Bananas |
Link |
- |
| 1011 |
Capacity To Ship Packages |
Link |
- |
Digit DP (count numbers with property)
long long dp[20][11][2][2]; string sN;
long long dfsDP(int i,int prev,bool tight,bool started){ if(i==(int)sN.size()) return started?1:0; auto &res=dp[i][prev+1][tight][started]; if(res!=-1) return res; res=0; int lim=tight?(sN[i]-'0'):9;
for(int d=0; d<=lim; ++d){ bool nt=tight && d==lim; bool ns=started||d!=0; if(!ns || prev==-1 || d!=prev) res+=dfsDP(i+1, ns?d:prev, nt, ns); }
return res; }
long long solveDP(long long N){ sN=to_string(N); memset(dp,-1,sizeof dp); return dfsDP(0,-1,1,0); }
| ID |
Title |
Link |
Solution |
| 233 |
Number of Digit One |
Link |
- |
| 902 |
Numbers At Most N Given Digit Set |
Link |
- |
| 1012 |
Numbers With Repeated Digits |
Link |
- |
Bitmask DP (TSP / subsets)
int tsp(const vector<vector<int>>& w){
int n=w.size(); const int INF=1e9; vector<vector<int>> dp(1<<n, vector<int>(n, INF));
dp[1][0]=0; for(int mask=1; mask<(1<<n); ++mask){ for(int u=0; u<n; ++u) if(dp[mask][u]<INF){ for(int v=0; v<n; ++v) if(!(mask&(1<<v))) dp[mask|1<<v][v] = min(dp[mask|1<<v][v], dp[mask][u]+w[u][v]); } }
return *min_element(dp.back().begin(), dp.back().end());
}
| ID |
Title |
Link |
Solution |
| 847 |
Shortest Path Visiting All Nodes |
Link |
- |
| 698 |
Partition to K Equal Sum Subsets |
Link |
- |
| 1340 |
Jump Game V |
Link |
Solution |
| 464 |
Can I Win |
Link |
- |
| 691 |
Stickers to Spell Word |
Link |
- |