动态规划

前提

• 最优子结构：问题的解可以通过组合子问题的解得到，即可以通过状态转移方程表示。

• 重叠子问题：求解过程中子问题重叠。

• 通常是求最值问题。

Knapsack

0/1

最大容量N，共M个物品，每个物品最多选一次。

状态方程：\(f[i][j]\)表示使用前\(i\)个物品，最大容量为\(j\)时可以获得的最大价值。

\[ \displaylines{ f[i][j] = \max(f[i-1][j], f[i-1][j-w[j]]+v[j]) \\ , 0 \le i \le M, 0 \le j \le N \\ } \]

边界条件：

• \(f[0][j] = 0\)
• \(f[i][0] = 0\)

const int M = 100 + 1; // object
const int N = 1000 + 1; // space

int ws[M];
int vs[M];

int dp[M][N];

int main() {
    // inputs
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ws[i] >> vs[i];
    }
    // init
    memset(dp, 0, sizeof(dp));
    // loop
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= ws[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-ws[i]]+vs[i]);
        }
    }
    // return
    cout << dp[m][n] << endl;
    return 0;
}

空间优化：

const int M = 100 + 1;
const int N = 1000 + 1;

int ws[M];
int vs[M];

int dp[N];

int main() {
    // inputs
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ws[i] >> vs[i];
    }
    // init
    memset(dp, 0, sizeof(dp));
    // loop
    for (int i = 1; i <= m; i++) {
        // reversed order! dp[i][j] only use dp[i-1][k] where k < j
        for (int j = n; j >= 1; j--) {
            if (j >= ws[i]) dp[j] = max(dp[j], dp[j-ws[i]]+vs[i]);
        }
    }
    // return
    cout << dp[n] << endl;
    return 0;
}

Complete

最大容量N，共M个物品，每个物品可以选任意次。

\[ \displaylines{ f[i][j] = \max_{0 \le k \le K}(f[i-1][j-kw[i]] + kv[i]) \\ f[i][j] = \max(f[i-1][j], f[i][j-w[i]]+v[i]) } \]

const int M = 100 + 1;
const int N = 1000 + 1;

int ws[M];
int vs[M];

int dp[M][N];

int main() {
    // inputs
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ws[i] >> vs[i];
    }
    // init
    memset(dp, 0, sizeof(dp));
    // loop
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= ws[i]) dp[i][j] = max(dp[i][j], dp[i][j-ws[i]]+vs[i]);
        }
    }
    // return
    cout << dp[m][n] << endl;
    return 0;
}

同样可以使用空间优化：

const int M = 100 + 1;
const int N = 1000 + 1;

int ws[M];
int vs[M];

int dp[N];

int main() {
    // inputs
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ws[i] >> vs[i];
    }
    // init
    memset(dp, 0, sizeof(dp));
    // loop
    for (int i = 1; i <= m; i++) {
        // ordered! dp[i][j] can use dp[i][j-ws[i]]
        for (int j = 1; j <= n; j++) {
            if (j >= ws[i]) dp[j] = max(dp[j], dp[j-ws[i]]+vs[i]);
        }
    }
    // return
    cout << dp[n] << endl;
    return 0;
}

贪心即可的情况

• 0/1背包，但所有物品的价值都一样。

  直接对物品重量从低到高进行排序，然后按顺序装入背包，直到达到最大容量即可。

  e.g. 最大雪糕数

  class Solution {
  public:
      int maxIceCream(vector<int>& costs, int coins) {
          sort(costs.begin(), costs.end());
          int res = 0;
          // don't fany parenthesis...
          while ((res < costs.size()) && ((coins -= costs[res]) >= 0)) {
              res++;
          }
          return res;
      }
  };
  

题目

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
public:
    int numSquares(int n) {
        // complete knapsack
        int m = sqrt(n) + 1;
        // init
        vector<int> dp(n + 1, 0x3f3f3f3f); // dp[1~n] should be inf
        dp[0] = 0; // but dp[0] is 0
        // loop
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j - i * i >= 0) dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};

最长公共子序列 LCS

子序列(Subsequence)可以不连续！(与最长公共子串不同)

经典动态规划解法\(O(n^2)\)：

dp[i][j]为使用前第一个字符串前i个字符、第二个字符串前j个字符时的LCS长度。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // init by max-size, to zeros.
        int dp[1005][1005];
        // start from 1, to avoid border detection.
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if (text1[i-1] == text2[j-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

最长上升子序列 LIS

DP solution \(O(n^2)\):

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1); // LIS ending at nums[i]
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

Greedy + Binary Search \(O(n \log n)\):

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> v; // keep track of the best LIS 
        for (int i = 0; i < n; i++) {
            int idx = lower_bound(v.begin(), v.end(), nums[i]) - v.begin();
            if (idx == v.size()) v.push_back(nums[i]);
            else v[idx] = nums[i];
        }
        return v.size();
    }
};

可以转换为LIS的LCS问题

如果两个序列中有一个序列的元素是各不相同的，则我们可以将这个序列视为一个排序关系，从而将LCS转换为另一个序列的LIS问题，从而\(O(n \log n)\)解决。

例题：（巧妙的使用map做替换）

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        int m = target.size(), n = arr.size();
        // build an order map
        map<int, int> M;
        for (int i = 0; i < m; i++) M[target[i]] = i;
        // LIS
        vector<int> v;
        for (int i = 0; i < n; i++) {
            // ignore those unmet elements!
            if (M.count(arr[i])) {
                int idx = lower_bound(v.begin(), v.end(), M[arr[i]]) - v.begin();
                if (idx == v.size()) v.push_back(M[arr[i]]);
                else v[idx] = M[arr[i]];
            }
        }
        return m - v.size();
    }
};

LIS的数量

需要记录额外的信息。

// dp ver.
class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> dp(n), cnt(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // 重置计数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};


// binary search ver.
class Solution {
    int binarySearch(int n, function<bool(int)> f) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (f(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

public:
    int findNumberOfLIS(vector<int> &nums) {
        vector<vector<int>> d, cnt;
        for (int v : nums) {
            int i = binarySearch(d.size(), [&](int i) { return d[i].back() >= v; });
            int c = 1;
            if (i > 0) {
                int k = binarySearch(d[i - 1].size(), [&](int k) { return d[i - 1][k] < v; });
                c = cnt[i - 1].back() - cnt[i - 1][k];
            }
            if (i == d.size()) {
                d.push_back({v});
                cnt.push_back({0, c});
            } else {
                d[i].push_back(v);
                cnt[i].push_back(cnt[i].back() + c);
            }
        }
        return cnt.back().back();
    }
};

最长公共子串

子串(Substring)必须连续！

动态规划\(O(n^2)\)：

dp[i][j]为以第一个字符串第i个字符、第二个字符串第j个字符结尾的字符串的最长公共子串长度。

需要使用额外的变量维护全局最长公共子串长度。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // init by max-size, to zeros.
        int dp[1005][1005];
        int res = 0;
        // start from 1, to avoid border detection.
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
                else dp[i][j] = 0;
            }
        }
        return res;
    }
};

最长公共子串（多序列）

(POJ Corporate Identity)

• KMP Brute Force

  N strings' LCS.

  Time Complexity: \(O(N^2L^2)\), L is the minimum length of the N strings.

  #define _CRT_SECURE_NO_WARNINGS
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  #include <algorithm>
  #include <string>
  
  using namespace std;
  
  const int maxn = 4005;
  const int maxc = 205;
  
  int Next[maxc];
  
  void getNext(string& p) {
    int l = p.length();
    Next[0] = -1;
    int i = 0, k = -1;
    while (i < l - 1) {
        while (k >= 0 && p[k] != p[i]) k = Next[k];
        i++, k++;
        if (p[k] == p[i]) Next[i] = Next[k]; 
        else Next[i] = k;
    }
  }
  
  int KMP(string& t, string& p) {
    int tlen = t.length();
    int plen = p.length();
    if (tlen < plen) return -1;
    int i = 0, j = 0;
    while (i < tlen && j < plen) {
        if (j == -1 || t[i] == p[j]) i++, j++;
        else j = Next[j];  
    }
    if (j == plen) return i - j;
    else return -1;
  }
  
  int N;
  string ss[maxn];
  int main() {
    while (cin >> N && N) {
        for (int i = 0; i < N; i++) cin >> ss[i];
        int len = ss[0].size();
          string ans;
        for (int i = len; i > 0; i--) {
            for (int j = 0; i + j <= len; j++) {
                string tmp = ss[0].substr(j, i);
                getNext(tmp);
                bool flag = true;
                for (int k = 1; k < N; k++) {
                    if (KMP(ss[k], tmp) == -1) {
                        flag = false;
                          break;
                    }
                }
                if (flag) {
                      // lexically longest
                    if(tmp.size()>ans.size()) ans = tmp;
                      else if(tmp.size()==ans.size() && tmp<ans) ans = tmp;
                }
            }
        }
          if(ans.empty()) cout << "IDENTITY LOST" << endl;
          else cout<<ans<<endl;
    }
  }
  

• KMP Binary Search

  \(O(L \log L*N^2)\)， enough for most problems !

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  #include <queue>
  #include <string>
  #include <vector>
  
  using namespace std;
  
  string ss[6];
  int N;
  
  bool check(int x) {
    for (int i = 0; i <= int(ss[0].size()) - x; i++) {
        string sub = ss[0].substr(i, x);
        bool flag = true;
        for (int i = 1; i < N; i++) {
            if (ss[i].find(sub) == -1) {
                flag = false;
                break;
            }
        }
        if (flag) return true;
    }
    return false;
  }
  
  int main() {
    cin >> N;
    string ans;
    for (int i = 0; i < N; i++) cin >> ss[i];
    int left = 0, right = 2005;
    while (left < right) {
        int mid = (left + right) / 2;
        if (check(mid)) left = mid + 1;
        else right = mid;
    }
    cout << left - 1 << endl;
  }
  

• Suffix Array

  Time Complexity: \(O(N^2\log L)\)

  Effective, but not always easy to write, anyway.

状态压缩

通常题目中会有一个序列（10~30长度），这个序列可以用二进制表示，即使用一个int表示这个序列的状态。

Wonderful Strings

如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。 给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。

子字符串 是字符串中的一个连续字符序列。

class Solution {
public:
    // substring problem, naive solution is to iterate begin:end, O(n^2)
    // problem size <= 10^5, so we need at most O(nlogn)
    long long wonderfulSubstrings(string word) {
        // to avoid O(n^2), we usually need a map to count different prefixes.
        unordered_map<int, int> cnt;
        cnt[0] = 1;
        long long ans = 0;
        // state compression, note 10 digits <= 2^10, can be represented with an integer.
        int mask = 0;
        for (int i = 0; i < word.size(); i++) {
            int c = word[i] - 'a';
            // current mask
            mask ^= (1 << c);
            // 0 odd: the same prefix mask
            ans += cnt[mask];
            // 1 odd: 10 types of suitable prefixes, add each count to ans.
            for (int j = 0 ; j < 10; j++) {
                int prefix = (mask ^ (1 << j));
                ans += cnt[prefix];
            }
            // update prefix map.
            cnt[mask]++;
        }
        return ans;
    }
};