动态规划合集 -- 动态规划的主程序不应该复杂，不然泛化能力差，过度拟合了

coin_change.cpp

// https://leetcode.com/problems/coin-change/
// 一堆硬币，给你个金额，你用最少的硬币数量合起来等于它，找不到返回-1

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


template <typename T>
void print_vector(vector<T> v) {
    cout << "size = " << v.size() << ": ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}


//dp[i] = min{dp[i-a[j]]}+1, for j in [1,n]
//dp[0] = 0
int coin_change(vector<int> a, int amount) {
    // dp: 使用 INT_MAX 作为没有找到分解方法的标记
    ///////////////// 不能使用INT_MAX，因为+1会越界
    const int MAX = amount+1;
    vector<int> dp(amount+1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < a.size(); j++) {
            if (i >= a[j]) {
                dp[i] = min(dp[i], dp[i-a[j]] + 1);
            }
        }
    }
    return dp[amount] != MAX ? dp[amount] : -1;
}


void test(vector<int> a, int amount, int result) {
    //print_vector(a);
    int ret = coin_change(a, amount);
    if (ret != result) {
        cout << "false result: " << ret << endl;
        cout << "test ";
        print_vector(a);
        cout << "test amount:" << amount << endl;
        assert(false);
    }
}



int main()
{
    test(vector<int>({}), 0, 0);
    test(vector<int>({2,5}), 0, 0);
    test(vector<int>({}), 1, -1);
    test(vector<int>({2}), 3, -1);
    test(vector<int>({2,5}), 6, 3);
    test(vector<int>({1}), 3, 3);
    test(vector<int>({2}), 4, 2);
    test(vector<int>({1,2,5}), 8, 3);
    test(vector<int>({1,2,5}), 10, 2);
    test(vector<int>({1,2,5}), 13, 4);
    test(vector<int>({474,83,404,3}), 264, 8);
    
    return 0;
}

coin_row.cpp

// 有一行硬币，挑选出若干硬币，这些硬币的和最大，并且任何两个硬币都不相邻。


#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


template <typename T>
void print_vector(vector<T> v) {
    cout << "size = " << v.size() << ", ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

//dp[i] = max{a[i-1]+dp[i-2], dp[i-1]}, for i > 1
//dp[0] = 0
//dp[1] = a[1]
int pick_up_coin(vector<int> a) {
    int n = a.size();
    if (n == 0) {
        return 0;
    }

    vector<int> dp(n+1, 0);
    dp[0] = 0;
    dp[1] = a[0]; // be care of here, first element of a at 0
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i-1]+dp[i-2], dp[i-1]); // be care of i-1
    }
    return dp[n];
}



void test(vector<int> a, int result) {
    //print_vector(a);
    int ret = pick_up_coin(a);
    if (ret != result) {
        cout << "false result: " << ret << endl;
        assert(pick_up_coin(a) == result);
    }
}

int main()
{
    test(vector<int>({1}), 1);
    test(vector<int>({1,2}), 2);
    test(vector<int>({1,2,3}), 4);
    test(vector<int>({1,3,2}), 3);
    test(vector<int>({5,1,2,10}), 15);
    test(vector<int>({5,1,4,2,10}), 19);
}

house_robber.cpp

// 198. House Robber
// 一个数列，不能取连续的两个，求最大和。其实就是coin row。

// dp[i] = max {dp[i-2] + A[i], dp[i-1] }, i >= 2
// dp[0] = 0, dp[1] = A[1]


typedef long long utype; // lintcode
//typedef int utype;     //leetcode

class Solution {
public:
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> A) {
        // write your code here
        if (rand() % 2)
            return rob1(A);
        return rob2(A);
    }
    
    long long rob1(vector<int> &A) {
        int n = A.size();
        if (!n) return 0;
        vector<utype> dp(n, 0);
        dp[0] = A[0];
        if (n > 1) dp[1] = max(A[0], A[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-1], dp[i-2]+A[i]);
        }
        return dp[n-1];
    }
    
    long long rob2(vector<int> &A) {
        utype n1 = 0; // dp[i-1]
        utype n2 = 0; // dp[i-2]
        for (int i = 0; i < A.size(); i++) {
            utype current = max(n1, n2 + A[i]);
            n2 = n1;
            n1 = current;
        }
        return n1;
    }
};

house_robber2.cpp

// 213. House Robber II
// https://leetcode.com/problems/house-robber-ii/

// 把圆化成直线
// 要么考虑第一个，不考虑最后一个
// 要么考虑最后一个，不考虑第一个

class Solution {
    int rob_in_line(vector<int> nums) {
        const int n = nums.size();
        if (n == 0) return 0;
        
        int n1 = nums[0];
        int n2 = 0;
        for (int i = 2; i <= n; i++) {
            int cur = max(n1, n2 + nums[i-1]);
            n2 = n1;
            n1 = cur;
        }
        return n1;
    }
    
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int rob_with_1 = rob_in_line(vector<int>(nums.begin(), nums.end()-1));
        int rob_with_n = rob_in_line(vector<int>(nums.begin()+1, nums.end()));
        return max(rob_with_1, rob_with_n);
    }
};

house_robber3.cpp

// 337. House Robber III
// https://leetcode.com/problems/house-robber-iii/


// 二叉树结构的村子，相邻的节点不能抢，求最大和。


// 不论几条线，要么是自己加孙子，要么是孩子。
// 一条线，是都是单传，是自己加一个孙子和一个孩子相比。
// 两条线，是自己加四个孙子，和两个孩子相比。


// 抢了当前位置，再加从孙子开始抢的结果
// 不抢当前位置，将从两个子树开始抢的结果
class Solution {
    int robber(TreeNode* node, int &l, int &r) {
        if (node == NULL) {
            return 0;
        }
        
        int ll, lr, rl, rr;
        ll = lr = rl = rr = 0;
        l = robber(node->left, ll, lr);
        r = robber(node->right, rl, rr);
        
        return max(node->val+ll+lr+rl+rr, l+r);
    }
    
public:
    int rob(TreeNode* root) {
        int l, r;
        return robber(root, l, r);
    }
};

LIS.cpp

// 最长递增子数列

// O(N^2)
// dp[i] = max{dp[j]+1 | [i] > [j], 0<=j<i}
// result: max{dp[i] | 0<=i<n}

class Solution {
    static const int bufsize = 10000;
    int dp[bufsize];
    
public:
    int lengthOfLIS(vector<int>& nums) {
        const int n = nums.size();
        if (n <= 1) return n;
        
        dp[0] = 1;
        int max_len = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
            max_len = max(max_len, dp[i]); // update the max length
        }
        return max_len;
    }
};


//--------------------------------------------------------------

// O(NlogN)
// "贪"
// 使用栈保存数据，约束是约束从小到大。
// 如果当前值比栈顶元素大，进栈。
// 否则，查找第一个大于等于该值的元素，执行替换。
// 这样在当前位置而言，栈的大小仍代表最大LIS的长度。
// 但又能让他继续添加，比当前位置大的元素入栈。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        vector<int> stack;
        stack.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > stack.back()) {
                // push
                stack.push_back(nums[i]);
            }
            else {
                int low = 0, high = stack.size()-1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (stack[mid] >= nums[i]) {
                        high = mid - 1;
                    }
                    else {
                        low = mid + 1;
                    }
                }
                stack[low] = nums[i];
            }
        }
        return stack.size();
    }
};

max_sub_array.cpp

// https://leetcode.com/problems/maximum-subarray/
// 具有最大和的连续子数组


#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


template <typename T>
void print_vector(vector<T> v) {
    cout << "size = " << v.size() << ", ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}


//dp[i] = dp[i-1] + a[i], d[i-1]>0, for i > 1
//dp[i] = a[i], else, for i > 1
//dp[0] = a[0]
int max_sub_array_sum(vector<int> a) {
    int n = a.size();
    if (n == 0) {
        return 0;
    }

    vector<int> dp(n, 0);
    dp[0] = a[0];
    int max_sum = a[0];
    for (int i = 1; i < n; i++) {
        dp[i] = a[i] + max(0, dp[i-1]);
        max_sum = max(max_sum, dp[i]);  // update max_sum
    }

    return max_sum;
}

// 精简为贪心：每个状态的最优解都从上一个状态的最优解得来
int max_sub_array_sum_2(vector<int> a) {
    int cur_sum = 0;
    int max_sum = 0;
    for (int i = 0; i < a.size(); i++) {
        cur_sum += a[i];
        cur_sum = max(cur_sum, 0);
        max_sum = max(max_sum, cur_sum);
    }
    return max_sum;
}


void test(vector<int> a, int result) {
    //print_vector(a);
    int ret = max_sub_array_sum_2(a);
    if (ret != result) {
        cout << "false result: " << ret << endl;
        print_vector(a);
        assert(false);
    }
}

int main()
{
    test(vector<int>({1}), 1);
    test(vector<int>({1,-5}), 1);
    test(vector<int>({1,-2,3}), 3);
    test(vector<int>({1,-1,5}), 5);
    test(vector<int>({5,-1,-2,10}), 12);
    test(vector<int>({5,1,-10,2,10}), 12);
}

MaximalSquare.cpp

// 221. Maximal Square   

/* 如果DP写起来很复杂，你肯定想错了，用相反的角度思考一下，也许才是对的。*/

/**
 * 更多讨论：
 * https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space
 * 列出了如何使用1维数组解决的方案，去手动模拟吧
 */

// v1: O(m*n)
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        const int m = matrix.size();
        if (m == 0) return 0;
        const int n = matrix[0].size();
        if (n == 0) return 0;
        
        int max_len = 0;
        vector<vector<int>> dp(m, vector<int>(n));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = matrix[i][j] - '0';
                if (i != 0 && j != 0 && dp[i][j] != 0) {
                    dp[i][j] = min( min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] ) + 1;
                }
                
                if (dp[i][j] > max_len) {
                    max_len = dp[i][j];
                }
            }
        }
        return max_len * max_len;
    }
};

palindrome partation2.cpp

// 给你个字符串，把它分解为回文的合集，问至少切几下（等价于最少分成几个回文-1）？
// 132. Palindrome Partitioning II

// 这里面有两个DP，第一个是DP求字符串是不是回文。
// 第二个求一个字符串最少可以分为几个回文。

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class Solution {
    static const size_t bufsize = 2000;
    bool palindrome[bufsize][bufsize];
    int dp[bufsize];
    string str;
 
public:
    int minCut(string s) {
        const int n = s.size();
        if (n <= 1) return 0;
        
        s.insert(s.begin(), 'x');
        str = s;
        
       
        // sub string: s[i,j] is palindrome or not
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= n; j++) {
        //         if (is_palindrome(i, j)) {
        //             palindrome[i][j] = true;
        //         } else {
        //             palindrome[i][j] = false;
        //         }
        //     }
        // }
        // DP的方式去判断字符串子串是不是回文
        // dp[i][j] = dp[i+1][j-1], for s[i]=s[j], i<j
        // dp[i][j] = true, for s[i]=s[j], i=j
        // 自后向前的DP1
        // for (int i = n; i >= 1; i--) {
        //     for (int j = i; j <= n; j++) {
        //         if (s[i]==s[j] && (j-i<2 || palindrome[i+1][j-1]) ) {
        //             palindrome[i][j] = true;
        //         } else {
        //             palindrome[i][j] = false;
        //         }
        //     }
        // }
        // 自前向后的DP2
        for (int i = 1; i <= n; i++) {
            // i在后，j在前
            for (int j = i; j >= 1; j--) {
                if (s[i] == s[j] && (i-j<2 || palindrome[j+1][i-1]) ) {
                    palindrome[j][i] = true;
                } else {
                    palindrome[j][i] = false;
                }
            }
        }

        // dp[i]: 长度为i的字符串分成回文的最小段数
        dp[0] = 0;
        dp[1] = 1;
        const int INF = (1<<30);
        for (int i = 2; i <= n; i++) {
            dp[i] = INF;
            for (int j = 0; j < i; j++) {
                if (palindrome[j+1][i]) {
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        
        return dp[n]-1;
    }
};


void test(string s, int result) {
    Solution so;
    int ret = so.minCut(s);

    if (ret != result) {
        cout << "test cast:" << endl << s << endl;
        cout << "true result: " << result << endl;
        cout << "false result: " << ret << endl;
        assert(false);
    }
}


int main()
{
    test("", 0);
    test("a", 0);
    test("aa", 0);
    test("aaa", 0);
    test("ab", 1);
    test("aab", 1);
    test("aabb", 1);
    test("aabba", 1);
    test("aabbaa", 0);
    test("aabaa", 0);
    test("aabccabcd", 6);
    return 0;
}

stock_with_cooldown.cpp

// 309. Best Time to Buy and Sell Stock with Cooldown

// 对于股票的题目，现在感觉更像是一种模拟题

// 刚开始时，我的钱为0，那么最后剩下的钱，就是我的收益。
// sell[i]: 卖掉i后，我还有的钱。
// buy[i]: 买i后，我还有多钱钱。
// 所以买入第0个后，buy[0] = -prices[0]。
// 卖出第0个后，sell[0] = 0.
// 对于卖有两种，一种是我昨天刚买的，今天卖掉：buy[i-1]+prices[i]。
// 另外一种是，昨天没卖，今天卖掉：sell[i-1]-prices[i-1]+prices[i]。
// 而对于买来讲，也分两种，如果是卖掉买，那我所依赖的是前天：sell[i-2]-prices[i]。
// 另外一种是，昨天没有买，今天买：buy[i-1]+prices[i-1]-prices[i]。

class Solution {
    static const int bufsize = 10000;
    int sell[bufsize], buy[bufsize];
    
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();
        if (n < 2) {
            return 0;
        }
        
        buy[0] = -prices[0];
        sell[0] = 0;
        int max_sell = 0;
        for (int i = 1; i < n; i++) {
            sell[i] = max(buy[i-1]+prices[i], sell[i-1]-prices[i-1]+prices[i]);
            max_sell = max(max_sell, sell[i]);
            if (1 == i) { // 边界条件，保证i-2有效
                buy[i] = buy[0] + prices[0] - prices[1];
            } else {
                buy[i] = max(sell[i-2]-prices[i], buy[i-1]+prices[i-1]-prices[i]);
            }
        }
        return max_sell;
    }
};

world_series_odds.cpp

// 有A，B两队，A硬的概率为p，不存在平局，谁先赢n场，谁就赢得比赛。
// P(i,j)，代表了A还差i场，B还差j场赢得比赛的概率。


#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <cmath>
#include <cstdio>

using namespace std;

#define SIZE 100
double dp[SIZE][SIZE];

template <typename T>
void print_vector(vector<T> v) {
    cout << "size = " << v.size() << ": ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

template <typename T>
void print_2d_array(T a[SIZE][SIZE], int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

double world_win(int n, double p) {
    memset(dp, -1, sizeof(dp));
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        for (int j = 1; j <= n; j++) {
            dp[i][j] = p * dp[i-1][j] + (1-p) * dp[i][j-1];
        }
    }

    //print_2d_array(dp, n);

    return dp[n][n];
}



void test(int n, double p, double result) {
    double ret = world_win(n, p);
    double error = fabs(ret-result);
    if (error > 1e-3) {
        cout << "true result: " << result << endl;
        cout << "test case is: " << n << " " << p << endl;
        cout << "false result: " << ret << endl;
        assert(false);
    }
}

int main()
{
    // n > 0
    test(1, 0.4, 0.4);
    test(2, 0.4, 0.352);
    test(7, 0.4, 0.228);
    return 0;
}

最长公共子序列变形.cpp

// 题目：cabbeaf:回文子序列有:c,a,aa,bb,,aba,abba,e,f,最长的就是abba,所以输出长度为4。
// 思路：求这个原字符串和它反转字符串的最长公共子序列(LCS)

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

template <typename Container>
void print_container(const Container& cont) {
    for (auto it = cont.begin(); it != cont.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}


const size_t bufsize = 10000;
int dp[bufsize][bufsize];
int max_palindrome(string s) {
    const int n = s.size();
    string str(s);
    reverse(str.begin(), str.end());
    s.insert(s.begin(), 'x');
    str.insert(str.begin(), 'x');

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i] == str[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[n][n];
}


void test(string s, int result) {

    int ret = max_palindrome(s);
    if (ret != result) {
        cout << "fail case:" << endl;
        cout << s << endl;
        cout << "true: " << result << endl;
        cout << "false: " << ret << endl;
    }
}


int main()
{
    test("", 0);
    test("a", 1);
    test("axbxb", 3);
    test("abcdcxb", 5);
    test("cabbeaf", 4);
    return 0;
}

背包问题.cpp

// 一个容量为W的包，一堆重量分别为w1...wn，价值分别为vi...vn的钻石，
// 问如何用包装下尽量多的钻石，让总价值最大。


#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <cmath>
#include <cstdio>

using namespace std;

#define SIZE 100
int dp[SIZE][SIZE];

template <typename T>
void print_vector(vector<T> v) {
    cout << "size = " << v.size() << ": ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

template <typename T>
void print_2d_array(T a[SIZE][SIZE], int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// 核心
int kp(vector<int>& w, vector<int>& v, int i, int j) {
    if (dp[i][j] >= 0) {
        return dp[i][j];
    }

    if (j < w[i]) {
        dp[i][j] = kp(w, v, i-1, j);
    } else {
        dp[i][j] = max(kp(w, v, i-1, j), v[i] + kp(w, v, i-1, j-w[i]));
    }
    return dp[i][j];
}


void test(vector<int> w, vector<int> v, int W, int result) {
    memset(dp, -1, sizeof(dp));
    int n = w.size();

    // 添加哑元，让w和v的数据从下标1开始
    w.insert(w.begin(), 0);
    v.insert(v.begin(), 0);
    
    // init
    for (int j = 0; j <= W; j++) {
        dp[0][j] = 0;
    }
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }    

    int ret = kp(w, v, n, W);

    // check the state table
    print_2d_array(dp, 6);

    if (ret != result) {
        cout << "true result: " << result << endl;
        cout << "test case is: " << endl;
        print_vector(w);
        cout << "false result: " << ret << endl;
        assert(false);
    }
}

int main()
{
    test( vector<int>({2,1,3,2}), vector<int>({12,10,20,15}), 5, 37 );
    test( vector<int>({3,2,1,4,5}), vector<int>({25,20,15,40,50}), 6, 65 );
    return 0;
}