Notebook

coin.cpp

// Given a set of coin values coins = {c1, c2, ..., ck}
// and a target sum of money n,
// form the sum n using as few coins as possible.
// You can use any coin as many times as you want.

#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#define INF (INT_MAX / 2)
using namespace std;

constexpr int MOD = 1e9 + 1;
constexpr int MAXN = 1e6 + 1;
vector<int> coins;

int solveRec(int n)
{
    if (n < 0)
        return INF;
    if (n == 0)
        return 0;
    int minsofar = INF;
    for (auto c : coins)
        minsofar = min(minsofar, solveRec(n - c) + 1);
    return minsofar;
}

int value[MAXN];
int solveRecDP(int x)
{
    if (x < 0)
        return INF;
    if (x == 0)
        return 0;
    if (value[x])
        return value[x];

    int minsofar = INF;
    for (auto c : coins)
        minsofar = min(minsofar, solveRecDP(x - c) + 1);
    return value[x] = minsofar;
}

int solveDP(int n)
{
    vector<int> table(n + 1, INF);
    table[0] = 0;
    for (int x = 1; x <= n; x++)
        for (auto c : coins)
            if (x - c >= 0 && table[x - c] + 1 < table[x])
                table[x] = table[x - c] + 1;
    return table[n];
}


// Constructing a solution
int first[MAXN]; // for each sum of money the first coin in an optimal solution
void solutionDP(int n)
{
    vector<int> table(n + 1, INF);
    table[0] = 0;
    for (int x = 1; x <= n; x++)
        for (auto c : coins)
            if (x - c >= 0 && table[x - c] + 1 < table[x])
            {
                table[x] = table[x - c] + 1;
                first[x] = c;
            }

    cout << "Number of coins: " << table[n] << "\n";
    while (n > 0)
    {
        cout << first[n] << " ";
        n -= first[n];
    }
    cout << "\n";
}


// counting the number of solutions
int cnt[MAXN];
int countSolution(int n)
{
    cnt[0] = 1;
    for (int x = 1; x <= n; x++)
        for (auto c : coins)
            if (x - c >= 0)
                cnt[x] = (cnt[x] + cnt[x - c]) % MOD;

    return cnt[n + 1];
}

int main(void)
{}

edit_distance.cpp

// Find the minimum number of editing operations needed to transform s into t.
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

// proceeds from right to left:
int editDist(const string &s, const string &t, int m, int n)
{
    // s is empty; insert t into s.
    if (m == 0)
        return n;

    // t is empty: remove all characters of s.
    if (n == 0)
        return m;

    // the last characters of the two are same.
    // ignore them and get count for remaining strings.
    if (s[m - 1] == t[n - 1])
        return editDist(s, t, m - 1, n - 1);

    // If last characters are not same, consider all three
    // operations on last character of first string, recursively
    // compute minimum cost for all three operations and take
    // minimum of three values.
    return 1 + min({
                   editDist(s, t, m, n - 1),    // Insert
                   editDist(s, t, m - 1, n),    // Remove
                   editDist(s, t, m - 1, n - 1) // Replace
               });
}

int editDist(const string &s, const string &t)
{
    return editDist(s, t, s.length(), t.length());
}

// proceeds from left to right:
int editDistDP(const string &s, const string &t)
{
    int m = s.length();
    int n = t.length();
    // table[i][j]: cost of converting s[..i) to t[..j)
    int table[m + 1][n + 1];

    table[0][0] = 0; // both are empty
    for (int i = 1; i <= m; i++)
        table[i][0] = i; // all insertions
    for (int j = 1; j <= n; j++)
        table[0][j] = j; // all deletions

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (s[i - 1] == t[j - 1]) // 0-based indexing
                table[i][j] = table[i - 1][j - 1];
            else
                table[i][j] = 1 + min({table[i][j - 1],       // Insert
                                       table[i - 1][j],       // Remove
                                       table[i - 1][j - 1]}); // Modify
        }

    return table[m][n];
}

int editDistDP2(const string &s, const string &t)
{
    int m = s.length();
    int n = t.length();
    vector<int> prev_row(n + 1), curr_row(n + 1);

    iota(prev_row.begin(), prev_row.end(), 0); // all deletions
    for (int i = 1; i <= m; i++)
    {
        curr_row[0] = i; // all insertions
        for (int j = 1; j <= n; j++)
            curr_row[j] = min({
                (s[i - 1] != t[j - 1]) + prev_row[j - 1], // Modify
                1 + curr_row[j - 1],                      // Insert
                1 + prev_row[j]                           // Delete
            });
        curr_row.swap(prev_row);
    }
    return prev_row[n];
}

int main(void)
{
    string s, t;
    cin >> s >> t;
    cout << editDist(s, t) << "\n";
    cout << editDistDP(s, t) << "\n";
    cout << editDistDP2(s, t) << "\n";
}

kadane.cpp

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;

/**
 * Returns the maximum subarray sum followed by the beginning and the ending 
 * indices of a solution.
 */
tuple<ll, int, int> kadane(vector<ll> &seq)
{
    ll max_sum = -1;
    int start, end; // [start, end]

    ll tmp_sum = 0;
    for (int i = 0, b = 0; i < seq.size(); i++)
    {
        tmp_sum += seq[i];
        if (tmp_sum > max_sum)
        {
            max_sum = tmp_sum;
            start = b;
            end = i;
        }
        else if (tmp_sum < 0)
        {
            tmp_sum = 0;
            b = i + 1;
        }
    }
    return {max_sum, start, end};
}

int main(void)
{
    int n;
    cin >> n;
    vector<ll> seq(n);
    for (int i = 0; i < n; i++)
        cin >> seq[i];

    ll max_sum;
    int a, b;
    tie(max_sum, a, b) = kadane(seq);
}

// Time Complexity: O(n)
// Memory Complexity: O(1)

knapsack_sum.cpp

// Given a list of weights determine all sums that can be constructed
// using the weights. A weight can be used at most once.
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXN = 1e5 + 1;
constexpr int MAXW = 1e2;
bool sum[MAXN];
int weights[MAXW];

// possible(x) -- can we construct a sum x with a subset of weights
bool possible(int n)
{
    sum[0] = true;
    for (auto w : weights)
        for (int x = n - w; x >= 0; x--)
            sum[x + w] |= sum[x];

    return sum[n];
}

int main(void){}

lcs.cpp

// Longest Common Subsequence
#include <iostream>
using namespace std;

// Returns length of LCS for s[0..m-1], t[0..n-1]
// it proceeds from right to left
int lcsRec(string s, string t, int m, int n)
{
    if (m == 0 || n == 0)
        return 0;
    if (s[m - 1] == t[n - 1])
        return 1 + lcsRec(s, t, m - 1, n - 1);
    else
        return max(lcsRec(s, t, m, n - 1), lcsRec(s, t, m - 1, n));
}
int lcsRec(string s, string t)
{ return lcsRec(s, t, s.length(), t.length()); }

int lcsDP(string s, string t)
{
    int m = s.length();
    int n = t.length();

    // table[i][j] contains length of LCS of s[..i) and t[..j)
    int table[m + 1][n + 1];
    for (int i = 0; i <= m; i++)
        table[i][0] = 0; // t is empty
    for (int i = 0; i <= n; i++)
        table[0][i] = 0; // s is empty

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (s[i - 1] == t[j - 1]) // 0-based indexing
                table[i][j] = 1 + table[i - 1][j - 1];
            else
                table[i][j] = max(table[i - 1][j], table[i][j - 1]);

    return table[m][n];
}

int main()
{
    string s = "AGGTAB";
    string t = "GsTsAYB";
    cout << "Length of LCS is " << lcsRec(s, t) << "\n";
    cout << "Length of LCS is " << lcsDP(s, t) << "\n";
}

lis.cpp

// Longest Increasing Subsequence
// Each element in the sequence must be larger than the previous one.
#include <iostream>
#include <vector>
using namespace std;

int LIS(vector<int> &seq)
{
    int n = seq.size();
    // length of the longest increasing subsequence that ends at position k:
    vector<int> length(n, 1);
    int msofar = 0;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < k; i++)
            if (seq[i] < seq[k])
            {
                length[k] = max(length[k], length[i] + 1);
                msofar = max(msofar, length[k]);
            }
    return msofar;
}

int main(void) {}

path_grid.cpp

// Compute the maximum sum on a path from (0,0) to (n, n).
// We can only move down or right.
#include <iostream>
#include <vector>
using namespace std;

// maximum sum on a path from the (0,0) to (x, y).
int sum(const vector<vector<int>> &grid, int x, int y)
{
    if (x == 0 && y == 0)
        return grid[0][0];
    if (x < 0 || y < 0)
        return 0;
    return max(sum(grid, x - 1, y), sum(grid, x, y - 1)) + grid[x][y];
}

int sumDP(const vector<vector<int>> &grid)
{
    int n = grid.size();
    int table[n][n];

    table[0][0] = grid[0][0];
    for (int i = 1; i < n; i++) {
        table[0][i] = table[0][i - 1] + grid[0][i];
        table[i][0] = table[i - 1][0] + grid[i][0];
    }

    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            table[i][j] = max(table[i - 1][j], table[i][j - 1]) + grid[i][j];

    return table[n - 1][n - 1];
}