Kopfkino

 #include <iostream> #include <vector> using namespace std; int rodCutting(int n, vector<int> &price) {     vector<int> dp(n + 1, 0);     for (int len = 1; len <= n; len++) {         for (int cut = 1; cut <= len; cut++) {             dp[len] = max(dp[len], price[cut - 1] + dp[len - cut]);         }     }     return dp[n]; } int main() {     int n;     cin >> n;     vector<int> price(n);     for (int i = 0; i < n; i++) cin >> price[i];     cout << rodCutting(n, price) << endl;     return 0; }

 #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Job {     int id;     int deadline;     int profit; }; bool compare(Job a, Job b) {     return a.profit > b.profit; } // DSU to find latest available slot int find(int parent[], int x) {     if (parent[x] == x)         return x;     return parent[x] = find(parent, parent[x]); } void merge(int parent[], int u, int v) {     parent[u] = v; } int main() {     int n;     cin >> n;     vector<Job> jobs(n);     int maxDeadline = 0;     for (int i = 0; i < n; i++) {         cin >> jobs[i].id >> jobs[i].deadline >> jobs[i].profit;         if (jobs[i].deadline > maxDeadline)             maxDeadline = jobs[i].deadline;     }   ...

#include <iostream> #include <vector> using namespace std; void kadaneWithSubarray(vector<int> &arr) {     int max_so_far = arr[0];     int max_ending_here = arr[0];     int start = 0, end = 0, temp_start = 0;     for (int i = 1; i < arr.size(); i++) {         if (arr[i] > max_ending_here + arr[i]) {             max_ending_here = arr[i];             temp_start = i;         } else {             max_ending_here += arr[i];         }         if (max_ending_here > max_so_far) {             max_so_far = max_ending_here;             start = temp_start;             end = i;         }     }     cout << "Max Subarray Sum: " ...

Top Down  int knapsack(int W, vector<int>& wt, vector<int>& val, int n, vector<vector<int>>& dp) {     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(W - wt[n-1], wt, val, n-1, dp),             knapsack(W, wt, val, n-1, dp)         );     else         return dp[n][W] = knapsack(W, wt, val, n-1, dp); } Bottom Up int knapsackBU(int W, vector<int>& wt, vector<int>& val, int n) {     vector<vector<int>> dp(n+1, vector<int>(W+1, 0));     for (int i = 1; i <= n; i++) {         for (int w = 0; w <= W; w++) {             if (wt[i-1] <= w)   ...

Bottom Up  #include <iostream> #include <vector> #include <string> using namespace std; int main() {     string X, Y;     cin >> X >> Y;     int m = X.length(), n = Y.length();     vector<vector<int>> dp(m+1, vector<int>(n+1));     // Build LCS table     for (int i = 1; i <= m; ++i)         for (int j = 1; j <= n; ++j)             if (X[i-1] == Y[j-1])                 dp[i][j] = dp[i-1][j-1] + 1;             else                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);     // Reconstruct LCS string     string lcs = "";     int i = m, j = n;     while (i > 0 && j > 0) {         if (X[i-1] == Y[j-1]) {            ...

Recurrence Relation Given dimensions of n matrices, find the most efficient way to multiply them with the minimum number of scalar multiplications. dp[i][j] = min(dp[i][k] + dp[k+1][j] + arr[i-1]*arr[k]*arr[j]) Bottom Up