ULTIMATE DSA MASTERY GUIDE
DYNAMIC PROGRAMMING
1. 0/1 Knapsack
const int N = 100;
const int W = 1000;
int dp[N][W];
int knapsack(int n, int w, vector<int>& wt, vector<int>& val) {
if (n == 0 || w == 0) return 0;
if (dp[n][w] != -1) return dp[n][w];
if (wt[n - 1] <= w) {
return dp[n][w] = max(val[n - 1] + knapsack(n - 1, w - wt[n - 1], wt, val),
knapsack(n - 1, w, wt, val));
} else {
return dp[n][w] = knapsack(n - 1, w, wt, val);
}
}
2. Unbounded Knapsack
int unboundedKnapsack(int n, int w, vector<int>& wt, vector<int>& val) {
vector<int> dp(w + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = wt[i]; j <= w; j++) {
dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
}
}
return dp[w];
}
3. Longest Increasing Subsequence (LIS)
int LIS(vector<int>& nums) {
int n = [Link]();
vector<int> dp(n, 1);
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
4. Edit Distance
int minDistance(string word1, string word2) {
int m = [Link](), n = [Link]();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) dp[i][j] = j;
else if (j == 0) dp[i][j] = i;
else if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
}
}
return dp[m][n];
}
GRAPHS
1. BFS
vector<int> bfs(int n, vector<int> adj[]) {
vector<int> ans;
vector<bool> vis(n, false);
queue<int> q;
[Link](0);
vis[0] = true;
while (![Link]()) {
int node = [Link](); [Link]();
ans.push_back(node);
for (int neighbor : adj[node]) {
if (!vis[neighbor]) {
vis[neighbor] = true;
[Link](neighbor);
}
}
}
return ans;
}
2. DFS
void dfs(int node, vector<int> adj[], vector<bool>& vis, vector<int>& ans) {
vis[node] = true;
ans.push_back(node);
for (int neighbor : adj[node]) {
if (!vis[neighbor]) dfs(neighbor, adj, vis, ans);
}
}
vector<int> getDFS(int n, vector<int> adj[]) {
vector<int> ans;
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) dfs(i, adj, vis, ans);
}
return ans;
}
3. Dijkstra's Algorithm
vector<int> dijkstra(int n, vector<pair<int, int>> adj[], int src) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(n, INT_MAX);
dist[src] = 0;
[Link]({0, src});
while (![Link]()) {
int u = [Link]().second;
[Link]();
for (auto& edge : adj[u]) {
int v = [Link], weight = [Link];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
[Link]({dist[v], v});
}
}
}
return dist;
}
STRINGS
1. Rolling Hash
const int P = 31;
const int MOD = 1e9 + 9;
long long computeHash(string s) {
long long hash = 0, p_pow = 1;
for (char c : s) {
hash = (hash + (c - 'a' + 1) * p_pow) % MOD;
p_pow = (p_pow * P) % MOD;
}
return hash;
}
2. Z-Function
vector<int> zFunction(string s) {
int n = [Link]();
vector<int> z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
return z;
}