dp | Jason Yuan's Blog

无标签

发布日期: 2020-07-06

文章字数: 249

title: 动态规划 Summary
date: 2020-07-06 14:52:26
author: Jason Yuan
tags:

Algorithm
Online Judge
categories: Online Judge

（1）动态规划

（1.1）数位 dp 学习

数位dp是一种计数用的dp，一般就是要统计一个区间 [le,ri] 内满足一些条件数的个数。

对应的暴力算法：

for(int i=le;i<=ri;i++)
    if(right(i)) ans++;

新的枚举：控制上界枚举，从最高位开始往下枚举，例如：ri=213，那么我们从百位开始枚举：百位可能的情况有0,1,2。
例一：HDU 2089 不要62

入门题。就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。

dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。
例题 [POJ 3252]

这题的约束就是一个数的二进制中0的数量要不能少于1的数量，通过上一题，这题状态就很简单了，dp[pos][num],到当前数位pos,0的数量减去1的数量不少于num的方案数，一个简单的问题，中间某个pos位上num可能为负数(这不一定是非法的，因为我还没枚举完嘛，只要最终的num>=0才能判合法，中途某个pos就不一定了)，这里比较好处理，Hash嘛，最小就-32吧(好像),直接加上32，把32当0用。这题主要是要想讲一下lead的用法，显然我要统计0的数量，前导零是有影响的。至于!lead&&!limit才能dp，都是类似的，自己慢慢体会吧。

（1.2）字符串 dp 复习

连个字符串之间的关系往往可以通过 dp 完成。（编辑距离 / 最长公共子序列 / ）

（1.3）博弈论 dp 学习

解：记 dp[i] 表示还剩 i+1 … n 时，先手的最大得分。（可能为负数）

状态转化函数：dp[i-1] = max(a[i] + a[i+1] + a[i+2] -dp[i+2], a[i] + a[i+1] - dp[i+1], a[i] - dp[i])
核心：博弈论题目可以考虑动态规划解法：后面的选择与之前怎么到达改状态无关。
状态转移推导：先手交换的思想。
code：（自己写的代码比较凌乱，就不贴了。）

（1.4）经典动态规划

最长公共子序列

// 动态规划求解并输出所有LCS
#include 
#include 
#include 
#include 
#include 
using namespace std;

string X = "ABCBDAB";
string Y = "BDCABA";
vector> table; // 动态规划表
set setOfLCS;      // set保存所有的LCS

int max(int a, int b)
{
    return (a>b)? a:b;
}

/**
 * 构造表，并返回X和Y的LCS的长度
 */
int lcs(int m, int n)
{
    // 表的大小为(m+1)*(n+1)
    table = vector>(m+1,vector(n+1));

    for(int i=0; i0 && j>0)
    {
        if (X[i-1] == Y[j-1])
        {
            lcs_str.push_back(X[i-1]);
            --i;
            --j;
        }
        else
        {
            if (table[i-1][j] > table[i][j-1])
                --i;
            else if (table[i-1][j] < table[i][j-1])
                --j;
            else   // 相等的情况
            {
                traceBack(i-1, j, lcs_str, lcs_len);
                traceBack(i, j-1, lcs_str, lcs_len);
                return;
            }
        }
    }

    string str(lcs_str.rbegin(), lcs_str.rend()); // lcs_str逆序
        if((int)str.size() == lcs_len)                // 判断str的长度是否等于lcs_len
            setOfLCS.insert(str);
}

void print()
{
    set::iterator beg = setOfLCS.begin();
    for( ; beg!=setOfLCS.end(); ++beg)
        cout << *beg << endl;
}
int main()
{
    int m = X.length();
    int n = Y.length();
    int length = lcs(m, n);
    cout << "The length of LCS is " << length << endl;

    string str;
    traceBack(m, n, str, length);
    print();

    getchar();
    return 0;
}

最长单调子序列：

直接 dp

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n=(int)nums.size();
        if (n == 0) return 0;
        vector dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心 + 二分查找

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) return 0;
        vector d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) d[++len] = nums[i];
            else{
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s1) {
        string  s2 = s1;
        reverse(s2.begin(), s2.end());//s2为s1的逆序列
        return longestCommonSubsequence(s1,s2);
    }

    //最长公共子序列函数
    int longestCommonSubsequence(string s1, string s2) {
           int l1 = s1.size(),l2=s2.size();
        int **dp = new int*[l1+1];
            for (int i = 0; i < l1+1; ++i) {
                    dp[i] = new int[l2+1]();
            }
        for (int i = 1; i < l1+1; i++) {
            for (int j = 1; j < l2+1; j++) {
                if (s1[i-1] == s2[j-1])    dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
            }
        }
        return dp[l1][l2];
    }
};

作者：njyang-yang-yang
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dong-tai-gui-hua-zui-jian-dan-si-lu-by-njyang-yang/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Jason Yuan

http://Columbine21.github.io/2020/07/06/dp/