## 单序列型 DP

### LC 300 最长递增子序列（LIS）

输入：nums = [10,9,2,5,3,7,101,18]



输入：nums = [0,1,0,3,2,3]



输入：nums = [7,7,7,7,7,7,7]



i  0 1 2 3 4 5
v  4 0 6 1 2 3
f  1 1 2 2 3 4


f (3) = ? 不知道



• $k < i$ 是切片约束。
• $v [k] < v [i]$ 是递增约束
• 最大的 f [k] 所对应的 k 是最长子序列约束

class Solution {
public:
int find_k(std::vector<int> &v, std::vector<int> &dp, int i) {
int max_vk = -1;
int find_k = -1;
for (int k = 0; k < i; k++) {
if (v[k] < v[i] && dp[k] > max_vk) {
max_vk = dp[k];
find_k = k;
}
}
return find_k;
}
int lengthOfLIS(vector<int> &v) {
auto n = v.size();
//dp [i] 表示以 v [i] 结尾的 v [0:i] 的 LIS
std::vector<int> dp(n);
dp[0] = 1;
auto llis = 1;
for (int i = 1; i < n; i++) {
auto k = find_k(v, dp, i);
if (k == -1) {
dp[i] = 1;
} else {
dp[i] = dp[k] + 1;
}
printf("dp = ");
print_vec(dp);
llis = max(dp[i], llis);
}
return llis;
}
};


class Solution {
public:
int lengthOfLIS(vector<int> &v) {
auto n = v.size();
if (n == 0)
return 0;
std::vector<int> dp(n);
dp[0] = 1;
int llis = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int k = 0; k < i; k++) {
if (v[k] < v[i]) {
dp[i] = max(dp[i], dp[k] + 1);
}
}
print_vec(dp);
llis = max(llis, dp[i]);
}
return llis;
}
};


### Game of 5 Powers

You are given a string S that consists of characters ‘0’ and ‘1’ only. Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5 (no leading zeros). If there is no such K, return -1 instead.

e.g. S=“101101101" return3 (101 = 5)

e.g. S=“1111101”return 1 (1111101 = 125)

e.g. S =“0000”return -1

e.g. S=“100" return -1

i  0 1 2 3 4 ............ n-1
v  1 0 1 0 0 ........... 0 1


i = 0, f (101101101)	可以，因为 101101101 不是 5^n
i = 1, 1 f (01101101) 不行，因为 1 不是 5^n
...
i = 3，101 f (101101) 可以，因为 101 是 5^n


bool isPowerOf5(string str){
if(str[0] == '0')
return false;
long num = 0;
for (char s : str){
num << 1;
if(s == '1')
num++;
}
while(num % 5 == 0) num/=5;
return num == 1;
}

int solve(string str) {
int n = str.size();
vector<int> dp(n);
fill(dp.begin(), dp.end(), -1);
for (int i = 0; i < n; i++){
if(isPowerOf5(substring(str, 0, i+1))) {
dp[i] = 1;
continue;
}
for (int j = 0; j < i; j++) {
string last = substring(str, j+1, i+1);
if(dp[j] == -1 || !isPowerOf5(last))
continue;
if(dp[i] == -1 || dp[i] > dp[j] + 1){
dp[i] = dp[j] + 1;
}
}
}
return dp[n-1];
}


## 双序列型 DP

### LC 1143. 最长公共子序列（LCS）

class Solution {
public:
int longestCommonSubsequence(string a, string b) {
auto n = a.size(), m = b.size();
vector<vector<int>>
dp (n + 1,vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

print_vec_2d(dp);
}
}
return dp[n][m];
}
};


class Solution {
public:
int longestCommonSubsequence(string a, string b) {
auto n = a.size(), m = b.size();
auto d = 2;
vector<vector<int>> dp(d,
vector<int>(m + 1, 0)); // 注意 dp 数组的大小
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[i % d][j] = dp[(i - 1) % d][j - 1] + 1;
} else {
dp[i % d][j] = max(dp[(i - 1) % d][j], dp[i % d][j - 1]);
}
}
}
return dp[n % d][m];
}
};



### LC 718. 最长公共字串


class Solution {
public:
int findLength(std::vector<int> &a, std::vector<int> &b) {
auto n = a.size(), m = b.size();
auto d = 2;
int maxval = 0;
vector<vector<int>> dp(d,
vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[i % d][j] = dp[(i - 1) % d][j - 1] + 1;
}
maxval = max(maxval, dp[i % d][j]);
}
}
return maxval;
}
};


class Solution {
public:
int findLength(std::vector<int> &a, std::vector<int> &b) {
int n = a.size(), m = b.size(), maxval = 0;
vector<int> dp(m + 1);
for (int i = 1; i <= n; i++) {
for (int j = m; j > 0; j--) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[j] = dp[j - 1] + 1;
maxval = max(maxval, dp[j]);
}else{
dp [j] = 0; // 这句不可少
}
}
}
return maxval;
}
};