# Dynamic Programming

## Classic basic DP Introduction

Practice Problems:
1. LeetCode 70
2. LeetCode 53
3. LeetCode 198
4. LeetCode 279

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if(len == 1) {
            return nums[0];
        }
        int dp[len];
        fill(dp, dp + len, 0);
        dp[0] = nums[0];
        dp[1] = max(dp[0], nums[1]);
        for(int i = 2; i < len; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[len - 1];
    }
};

## LIS
* [LIS](https://hackmd.io/@PeterWang/LIS)

## LCS
Practice Problems:
1. [LeetCode 1143](https://leetcode.com/problems/longest-common-subsequence/)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length(), len2 = text2.length();
        int dp[len1 + 1][len2 + 1];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                dp[i][j] = max(max(dp[i][j], dp[i - 1][j]), dp[i][j - 1]);
            }
        }
        return dp[len1][len2];
    }
};

## Knapsack Problem
Practice Problems:
1. [leetcode 322. Coin Change](https://leetcode.com/problems/coin-change/description/)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[amount + 1];
        fill(dp, dp + amount + 1, 1e4 + 1);
        dp[0] = 0;
        for(int i = 0; i < coins.size(); i++) {
            for(int j = 1; j <= amount; j++) {
                if(j >= coins[i]) {
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] > 1e4) return -1;
        return dp[amount];
    }
};

2. leetcode 494. Target Sum
3. leetcode 474. Ones and Zeroes
4. leetcode 279. Perfect Squares
5. leetcode 322. Coin Change
6. leetcode 377. Combination Sum IV
7. leetcode 474. Ones and Zeroes
8. leetcode 494. Target Sum
9. leetcode 983. Minimum Cost For Tickets
10. leetcode 1049. Last Stone Weight II
11. leetcode 1262. Greatest Sum Divisible by Three
12. leetcode 1449. Form Largest Integer With Digits That Add up to Target
13. leetcode 377. Combination Sum IV

## AtCoder DP contest
* [reference](https://atcoder.jp/contests/dp)
1. Frog 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

#define pb push_back
#define ll long long

const int MAXN = 1e5 + 4;
int n;
int arr[MAXN];

int main() {
    while(cin >> n) {
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int dp[n];
        dp[0] = 0;
        dp[1] = abs(arr[1] - arr[0]);
        for(int i = 2; i < n; i++) {
            dp[i] = min(abs(arr[i] - arr[i - 1]) + dp[i - 1], abs(arr[i] - arr[i - 2]) + dp[i - 2]);
        }
        cout << dp[n - 1] << endl;
    }
}

2. Frog 2

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

#define pb push_back
#define ll long long

const int MAXN = 1e5 + 1;
int n, k;
int arr[MAXN];

int main() {
    while(cin >> n >> k) {
        int dp[n];
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
            dp[i] = 1e9 + 7;
        }
        dp[1] = 0;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                if(i - j >= 1) {
                    dp[i] = min(dp[i - j] + abs(arr[i - j] - arr[i]), dp[i]);
                }
            }
        }
        cout << dp[n] << endl;
    }
}

3. Vacation

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

#define pb push_back
#define ll long long

const int MAXN = 1e5 + 1;
int n;

struct happiness {
    int a;
    int b;
    int c;
};

int maxn(int a, int b, int c) {
    return max(max(a, b), c);
}

int main() {
    while(cin >> n) {
        happiness happ[MAXN];
        int dpa[n + 1], dpb[n + 1], dpc[n + 1];
        for(int i = 1; i <= n; i++) {
            cin >> happ[i].a >> happ[i].b >> happ[i].c;
            dpa[i] = 0;
            dpb[i] = 0;
            dpc[i] = 0;
        }
        dpa[1] = happ[1].a;
        dpb[1] = happ[1].b;
        dpc[1] = happ[1].c;
        for(int i = 2; i <= n; i++) {
            dpa[i] = max(dpb[i - 1], dpc[i - 1]) + happ[i].a;
            dpb[i] = max(dpa[i - 1], dpc[i - 1]) + happ[i].b;
            dpc[i] = max(dpa[i - 1], dpb[i - 1]) + happ[i].c;
        }
        cout << maxn(dpa[n], dpb[n], dpc[n]) << endl;
    }
}

4. Knapsack 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

#define pb push_back
#define ll long long

const int MAXN = 1e5 + 1;
int N, W;
int w[101], v[101];

int main() {
    while(cin >> N >> W) {
        ll dp[W + 1];
        fill(dp, dp + W +1, 0);
        for(int i = 0; i < N; i++) {
            cin >> w[i] >> v[i];
        }
        for(int i = 0; i < N; i++) {
            for(int j = W; j >= w[i]; j--) {
                dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
            }
        }
        cout << dp[W] << endl;
    }
}

5. Knapsack 2

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <climits>

using namespace std;

#define pb push_back
#define ll long long

const ll MAXN = INT_MAX;
ll N, W;
ll w[101], v[101];

int main() {
    while(cin >> N >> W) {
        ll total = 0;
        for(ll i = 0; i < N; i++) {
            cin >> w[i] >> v[i];
            total += v[i];
        }
        ll dp[total + 1];
        fill(dp, dp + total + 1, INT_MAX);
        dp[0] = 0;
        for(ll i = 0; i < N; i++) {
            for(ll j = total; j >= v[i]; j--) {
                dp[j] = min(dp[j - v[i]] + w[i], dp[j]);
            }
        }
        ll ans = -1;
        for(ll i = 0; i <= total; i++) {
            if(dp[i] <= W) {
                ans = max(ans, i);
            }
        }
        cout << ans << endl;
    }
}

6. LCS

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <climits>

using namespace std;

#define pb push_back
#define ll long long

string a, b, ans;
int len[3001][3001];

void sub(int lena, int lenb) {
    if(lena == 0 || lenb == 0) return;
    if(a[lena - 1] == b[lenb - 1]) {
        ans = a[lena - 1] + ans;
        sub(lena - 1, lenb - 1);
    } else {
        if(len[lena - 1][lenb] > len[lena][lenb - 1]) {
            sub(lena - 1, lenb);
        } else {
            sub(lena, lenb - 1);
        }
    }
}

int main() {
    while(cin >> a >> b) {
        int lena = a.length(), lenb = b.length();
        ans  = "";
        memset(len, 0, sizeof(len));
        for(int i = 1; i <= lena; i++) {
            for(int j = 1; j <= lenb; j++) {
                if(a[i - 1] == b[j - 1]) {
                    len[i][j] = len[i - 1][j - 1] + 1;
                } else {
                    len[i][j] = max(len[i - 1][j], len[i][j - 1]);
                }
            }
        }
        sub(lena, lenb);
        cout << ans << endl;
    }
}