Sample solutions for each of above problem type:

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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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-2/
https://leetcode.com/problems/combination-sum-iv/
https://leetcode.com/problems/perfect-squares/
https://leetcode.com/problems/minimum-cost-for-tickets/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	int minScoreTriangulation(vector<int>& A) {

		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];
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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];
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
	bool PredictTheWinner(vector<int>& nums) {
		int n = nums.size();

		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/

Sample solutions for each of above problem type:#

Sample solutions for each of above problem type: