01背包问题：
LC494 目标和[装满解的数目]
完全背包问题：
LC279 完全平方数
 LC322 Coin Change
LC518 Coin Change 2
二维费用的背包问题：
LC474 Ones and Zeroes

推荐读物：

背包九讲
《算法设计指南（第2版）》，第8章动态规划，Steven S.Skiena著，谢勰译，清华大学出版社。
一个方法团列6道股票问题, 作者：labuladong

子序列/子串

最长连续序列

用一个hashmap记录数字x 对应其所在的连续序列的长度
遍历该数组，对于每个数字n：
- 如果hashmap中存在数字n，则跳过n，以去掉重复数组
- 如果hashmap中不存在数字n，则n所在的连续序列的长度为l + r + 1：
  - l：n - 1所在的连续序列的长度
  - r：n + 1所在的连续序列的长度 1
  - n - 1和n + 1所在的连续序列的长度可由hashmap中查到。如果hashmap中不存在以n - 1和n + 1为key的项，则认为其所在的连续序列的长度为0。
- 更新n，n + l，n - r所在序列的长度为上面所求的n所在序列的长度。
- 只更新n + l和n - r，而不是n - r和n + l之间所有存在的点，是因为如果还要想扩大该序列的长度，必然需要在该序列的两侧增加节点。如果遇到一个在该序列内部的节点，不能增大该序列的长度，因此记录也没用。
- n在n + l和n - r之间，但需要更新n的原因是为了去重。再次遇到n的时候避免重复计算。
找到所有连续序列长度的最大值，即为所求。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
      auto mp = unordered_map<int, int>{};
      auto ans = 0;
      for(auto x : nums)
      {
        cout<<x<<" ";
        if(mp.find(x) == mp.end())
        {
          int l = mp.find(x - 1) == mp.end() ? 0 : mp[x - 1];
          int r = mp.find(x + 1) == mp.end() ? 0 : mp[x + 1];
          mp[x - l] = mp[x + r] = l + r + 1;
          ans = max(ans, l + r + 1);
        }
      }

      return ans;
    }
};

最大子串和

LC53 最大子序和

设下标为$i$位置处的最大子串和为$f(i)$。则

当$i$位置处的最大子串包含$i$位置的元素时，$f(i) = a_i + f(i - 1)$
当$i$位置处的最大子串不包含$i$位置的元素时，因为子串不能断开，因此$f(i) = a_i$。
则最大子串和$f(i) = \text{max}(a_i + f(i - 1), a_i)$

状态转移方程只和前一状态相关，因此只用一个变量就可以描述状态。

code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      auto pre = 0;
      auto ans = nums.front();

      for(auto n : nums)
      {
        pre = max(pre + n, n);
        ans = max(pre, ans);
      }

      return ans;
    }
};

编辑距离

设模式串为P，文本串为T。我们定义对文本串T上某个字符$T[k]$的三种操作：

替换：将文本串上的字符$T[k]$替换成另一个字符$c$。记替换代价为$\mathrm{match}(T[k], c)$。一般我们认为：
- 如果两个字符相同，则不需要付出代价，即$\mathrm{match}(a, a) = 0$。
- 如果两个字符不同$a \neq b$，则需要付出$\mathrm{match}(a, b) = 1$的代价。
插入：在文本串$T$上的字符$T[k]$之后插入一个字符$c$。
删除：删除文本串$T$上的字符$T[k]$。

定义$Si = [s_1, s_2, \cdots, s_i]$为序列S的一个前缀，且$S_0 = \varnothing$为空。我们一般考虑的编辑距离都是对称的$d(i, j) = d(j, i)$，所以我们可以认为被修改的对象是文本串$T$，也可以等价的认为被修改的对象是模式串$P$。
$P_i$到$T_j$的编辑距离$d(i,j)$是下面三种操作所产生的编辑距离当中的最小值，则我们有：$d(i, j) = \mathrm{max}(d{\mathrm{substitute}}(i,j), d{\mathrm{insert}}(i,j), d{\mathrm{insert}}(i,j))$

我们认为被修改的是文本串$T$：

状态转移方程：

替换：
- 尝试将文本串中的T[j]替换为模式串中的P[i]的费用：$\mathrm{match}(P[i], T[j])$
- 匹配剩余部分$P{i - 1}$和$T{j - 1}$的费用：$d(i - 1, j - 1)$。
- 总费用为两者之和：$d_{\mathrm{substitute}}(i,j) = d(i - 1, j - 1) + \mathrm{match}(P[i], T[j])$
插入：
- 在文本串字符$T[j]$之后插入模式串字符$P[i]$的费用：$\mathrm{insert}(P[i])$
- 匹配剩余部分$P{i - 1}$ 和 $T{j}$的费用：$d(i - 1, j)$
- $d_{\mathrm{insert}}(i,j) = d(i - 1, j) + \mathrm{insert}(P[i])$
删除：
- 删除掉文本串字符$T[j]$的费用：$\mathrm{delete}(T[j])$
- 匹配剩余部分$P{i}$ 和 $T{j - 1}$的费用：$d(i, j - 1)$
  $d_{\mathrm{insert}}(i,j) = d(i, j - 1) + \mathrm{delete}(T[j])$

初始化：

$d(i,0)$的含义为：模式串$P{i}$和文本串$T{0} = \varnothing$的匹配距离。为了正确匹配我们只能不断地向文本串中增加字符。因此有：
$d(i,0) = d(i - 1, 0) + \mathrm{insert}(P[i])$

$d(0,j)$的含义为：模式串$P{0} = \varnothing$和文本串$T{j}$的匹配距离。为了正确匹配我们只能不断地删除文本串上的字符。因此有：
$d(0,j) = d(0, j - 1) + \mathrm{delete}(T[j])$

类似地，我们也可以认为被修改的是模式串$P$：

状态转移方程：

替换：
- 尝试将模式串中的P[i]替换为文本串中的T[j]的费用：$\mathrm{match}(T[j], P[i])$
- 匹配剩余部分$P{i - 1}$和$T{j - 1}$的费用：$d(i - 1, j - 1)$。
- 总费用为两者之和：$d_{\mathrm{substitute}}(i,j) = d(i - 1, j - 1) + \mathrm{match}(T[j], P[i])$
插入：
- 在模式串字符$P[i]$之后插入文本串字符$T[j]$的费用：$\mathrm{insert}(T[j])$
- 匹配剩余部分$P{i - 1}$ 和 $T{j}$的费用：$d(i, j - 1)$
- $d_{\mathrm{insert}}(i,j) = d(i, j - 1) + \mathrm{insert}(T[j])$
删除：
- 删除掉模式串字符$P[i]$的费用：$\mathrm{delete}(P[i])$
- 匹配剩余部分$P{i - 1}$ 和 $T{j}$的费用：$d(i - 1, j)$
  $d_{\mathrm{insert}}(i,j) = d(i - 1, j) + \mathrm{delete}(P[i])$

初始化：

$d(i,0)$的含义为：模式串$P{i}$和文本串$T{0} = \varnothing$的匹配距离。为了正确匹配我们只能不断地删除模式串中的字符。因此有：
$d(i,0) = d(i - 1, 0) + \mathrm{delete}(P[i])$

$d(0,j)$的含义为：模式串$P{0} = \varnothing$和文本串$T{j}$的匹配距离。为了正确匹配我们只能不断地增加模式串上的字符。因此有：
$d(0,j) = d(0, j - 1) + \mathrm{insert}(T[j])$

两个空串的编辑距离一般定义为0
$d(0,0) = 0$

$P_m$和$T_n$的编辑距离的目标单元为d(m, n)，即dp矩阵的右下角。

LC72 编辑距离
这是一个将插入和删除费用设置为常数1，替换则是相等为0，不等为1的题目。正常初始化。

code

class Solution {
public:
    int minDistance(string word1, string word2) {
        auto m = word1.size() + 1;
        auto n = word2.size() + 1;
        auto dp = vector<vector<int>>(m, vector<int>(n, 0));

        // fill in the base cases
        iota(dp.front().begin(), dp.front().end(), 0);
        
        for(size_t i = 0; i < m; ++i)
        {
            dp[i][0] = i;
        }

       

        for(size_t i = 1; i < m; ++i)
        {
            for(size_t j = 1; j < n; ++j)
            {
                dp[i][j] = min({
                    dp[i - 1][j - 1] + match(word1[i - 1], word2[j - 1]),
                    dp[i][j - 1] + 1,
                    dp[i - 1][j] + 1
                });
            }
        }

        return dp.back().back();
    }

    static int match(char lhs, char rhs)
    {
        return lhs == rhs ? 0 : 1;
    }

};

LCS

LC1143 Longest Common Subsequence

思路一：

令$X = [x_1, x_2, x_3, \cdots, x_m]$, $Y = [y_1, y_2, y_3, \cdots, y_n]$, $Z = [z_1, z_2, z_3, \cdots, z_k]$。Z为X和Y的任意一个LCS。定义$S_i = [s_1, s_2, \cdots, s_i]$为序列S的一个前缀，且$S_0 = \varnothing$为空。则有以下三个推论：

如果 $x_m = y_n$，则有：
- $z_k = x_m = y_n$
- $z{k-1}$是$X{m-1}$和$Y_{n - 1}$的一个LCS。
如果 $xm \neq y_n$，则$z_k \neq x_m \Rightarrow$ $Z$ 是 $X{m -1}$和$Y_{n}$的一个LCS。
如果 $xm \neq y_n$，则$z_k \neq y_n \Rightarrow$ $Z$ 是 $X{m}$和$Y_{n - 1}$的一个LCS。

证明：

如果 $x_m = y_n$：
- 假设$z_k \neq x_m$，则我们现在把$x_m = y_n$放在$Z$这个序列的末尾，就会形成一个长度为$k+1$的LCS，这和$Z$是$X$和$Y$的一个LCS相矛盾。
- 假设存在这样一个序列$M$，它的长度$l$比Z_{k-1}的长度$k-1$长。那么我们把$x_m = y_n$放在$M$的末尾，就会形成一个长度为$l + 1$的序列，并且$l + 1 > k - 1 + 1 = k$，这与$Z$是$X$和$Y$的一个LCS相矛盾。
如果 $xm \neq y_n$ 并且 $z_k \neq x_m$：
$Z$必然也是$X{m - 1}$和$Y$的一个CS。假设$M$是一个$X_{m - 1}$和$Y$的CS，且$M$的长度大于$k$，那么$M$必然也是$X$和$Y$的CS。然而$X$和$Y$的LCS的长度才只有$k$，这和假设相矛盾。
同2

通过以上三个推论，我们知道：

如果$xm = y_n$，想要找到$X$和$Y$的LCS，我们需要先找到$X{m - 1}$和$Y_{n - 1}$的LCS。
如果$xm \neq y_n$，想要找到$X$和$Y$的LCS，我们需要先找到$X{m - 1}$和$Y{n}$的LCS与$X{m}$和$Y_{n - 1}$的LCS中的较长者。
设状态$c[i, j]$为$X_i$和$Y_j$的LCS的长度，则状态转移方程：

c[i, j] = c[i - 1, j - 1] + 1, if X[i] == Y[j] && i > 0 && j > 0
c[i, j] = max(c[i -1, j], c[j - 1, i]), if X[i] != Y[j] && i > 0 && j > 0

初始化：
c[i, j] = 0, if i = 0 || j = 0

注意到i和j都依赖到i - 1和j - 1，所以我们需要从按i从小到大，j从小到大来填表。注意这里两个序列的下标是从1开始的，因此i一共有$0 \cdots m$一共$m + 1$种取值。同理j也有$n + 1$种取值。我们需要初始化一个$(m + 1) \times (n + 1)$的矩阵来完成填表。

code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        auto m = text1.size() + 1;
        auto n = text2.size() + 1;

        // initilize the dp matrix, initialize it with zeros 
        auto dp = vector<vector<int>>(m, vector<int>(n, 0));

        // the row i == 0 and the col j == 0 have already been 
        // intialized as zeros
        for(size_t i = 1; i < text1.size() + 1; ++i)
        {
            for(size_t j = 1; j < text2.size() + 1; ++j)
            {
                if(text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[m - 1][n - 1];
    }
};

空间上的改进：

注意到c[i, j]的状态仅仅和c[i - 1, j],c[i, j - 1],c[i - 1, j - 1]相关。因此我们可以只用两行长度为i的数组就能完成填表。但是这仅仅适用于求LCS的长度，不可能只靠这两行来恢复LCS序列。

思路二：

LCS问题可被证明通过编辑距离解决。我们需要在计算编辑距离的时候禁用字符串替换。将编辑距离中的match函数改写为：

如果字符a == b，返回0
如果字符a != b，返回一个绝不可能取到的值（比如两个带匹配串的最大长度）或二倍的插入距离。

这样得到的编辑距离和LCS的关系是(来自Longest common subsequence, Wikipedia)：
$d(X, Y) = m + n - 2 * |LCS(x,y)|$
其中m是X串的长度，n是Y串的长度

通过编辑距离求解

class Solution {
public:
    int longestCommonSubsequence(string word1, string word2) {

        auto m = word1.size() + 1;
        auto n = word2.size() + 1;
        auto max_len = max(m - 1, n - 1);
        auto dp = vector<vector<int>>(m, vector<int>(n, 0));

        // fill in the base cases
        iota(dp.front().begin(), dp.front().end(), 0);
        
        for(size_t i = 0; i < m; ++i)
        {
            dp[i][0] = i;
        }

       

        for(size_t i = 1; i < m; ++i)
        {
            for(size_t j = 1; j < n; ++j)
            {
                dp[i][j] = min({
                    dp[i - 1][j - 1] + match(word1[i - 1], word2[j - 1], max_len),
                    dp[i][j - 1] + 1,
                    dp[i - 1][j] + 1
                });
            }
        }
        auto dis = dp.back().back();
        auto lcs_len = (static_cast<int>(m + n - 2) - dis) / 2;
    
        return lcs_len;
    }

    static int match(char lhs, char rhs, int max)
    {
        return lhs == rhs ? 0 : max;
    }

};

LIS

LC300 Longest Increasing Subsequence

状态转移方程：

$P_i = \max_{0 \leq j < i}\left\{P_j | N_i < N_j\right\} + 1$ $P_0 = 0$

思路一：

初始化dp数组值全部为1，即最长上升子序列最小也是1。
自底向上遍历时时会自动保持条件j < i。判断nums[j] < nums[i]，如果成立，就找到尝试更新dp[i]。

code

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() < 2) return nums.size();
        auto res = 0;
        auto dp = vector<int> (nums.size(), 1);
        for(int i = 0; i < nums.size(); ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                    // update dp[i] if we found such j
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            // find the maximum in dp[]
            res = max(res, dp[i]);
        }
        return res;

    }
};

❓思路二[仍然不是很理解]：

每次计算dp[i]的时候需要查询所有的j < i，查询时间为线性。我们尝试优化该查询时间。我们重新定义dp[]状态数组：dp[i]是长度为i的最长上升子序列的最小末尾。可以证明如果给定$i < j$则必然有$dp[i] < dp[j]$。我们用反证法来证明上述结论：

假设$i < j$时，有$dp[i] \geq dp[j]$。因为$j > i$，所以我们必然可以从数组$dp[j]$上裁剪下来一个长度为$i$的子数组。因为是上升序列，则裁剪下来的子树组的末尾元素必然比原数组的末尾元素要小。因此存在一个长度是i，但末尾值比dp[j]要小的子序列。这和dp[i] > dp[j]矛盾。

因此新的状态数组dp[i]必然是递增的。我们就可以在这个有序数组上做二分查找。

如果dp数组中存在dp[j] > nums[i]，则更新dp[j] = nums[i]。因为此时我们完全可以用nums[i]来替代dp[j]。
如果dp数组中不存在dp[j] > nums[i]，则nums[i]可以接在dp[last]位置，形成更长的递增子序列。因此将nums[i]放入dp数组尾部。
最后dp数组的长度即为所求。

Feb/20/2020 code

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        auto dp = vector<int>{};
        for(auto n : nums)
        {
            if (auto it = lower_bound(dp.begin(), dp.end(), n);
               it == dp.end())
            {
                // we cannot find a bigger tail, we could expand 
                // the sequence
                dp.push_back(n);                
            }
            else if (*it > n)
            {
                // we found a smaller tail end of the sequence 
                *it = n;
            }
        }
        return dp.size();
    }
};

code

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        auto dp = vector<int>{};
        for(auto num : nums)
            if(auto it = lower_bound(dp.begin(), dp.end(), num);
               it == dp.end()) dp.push_back(num);
            else if(num < *it) *it = num;
        return dp.size();
    }
};

思路三：
指定终点的最长路径问题：将数组中所有的数$N_i$看作图的顶点，如果$j < i$且$N_j < N_i$则存在边$(i, j)$。并定义$N_0 = -\infty$。求$\mathrm{path}(N_i, N_0)$的最大长度。

思路四：

可以证明最大单调子序列问题可以通过LCS来求解

复制一份待求LIS的数组，记原来数组为T，复制的数组为P。
将P排序后去重。
求T和P的LCS，即是T和P的LIS。

code

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        auto nums2 = vector<int>(nums);
        sort(nums2.begin(), nums2.end());
        nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end());
        return longestCommonSubsequence(nums, nums2);
    }

    int longestCommonSubsequence(vector<int> text1, vector<int> text2) {
        auto m = text1.size() + 1;
        auto n = text2.size() + 1;

        // initilize the dp matrix, initialize it with zeros 
        auto dp = vector<vector<int>>(m, vector<int>(n, 0));

        // the row i == 0 and the col j == 0 have already been 
        // intialized as zeros
        for(size_t i = 1; i < text1.size() + 1; ++i)
        {
            for(size_t j = 1; j < text2.size() + 1; ++j)
            {
                if(text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[m - 1][n - 1];
    }
};

LIS变形：
面试题17.08 马戏团人塔
 LC354 俄罗斯套娃信封问题

将一个维度排好顺序（这里假设是高度h），在另一个维度上寻找LIS。但是高度相同的信封是无法套在一起的。如果简单地按照字典序进行排序的话，会导致类似(55, 60) -> (55, 61)也被认为是有效的序列。为了避免这种情况，我们将第二个维度按逆序排序。(55, 61), (55, 60)。这样在LIS进行时，因为要求“序列”（即下标必须递增），这两个信封就不会被认为可以套在一起。

code

class Solution {
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        auto indices = vector<size_t>(height.size());
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](auto lhs, auto rhs)
        {
            return height[lhs] == height[rhs] ? 
                   weight[lhs] > weight[rhs]  : 
                   height[lhs] < height[rhs]  ;
        });

        auto dp = vector<int>{weight[indices.front()]};
        for(auto i = size_t{1}; i < indices.size(); ++i)
        {
            if(auto w = weight[indices[i]];
                w > dp.back())
            {
                dp.push_back(w);
            }
            else
            {
                *lower_bound(dp.begin(), dp.end(), w) 
                    = w;
            }
        }

        return dp.size();
    }
};

最长公共子串

子串要求字符串是连续的。设dp[i, j]为以字符X[i]和Y[j]为结尾的最长公共子串的长度。则状态转移方程为
dp[i][j] = dp[i - 1][j - 1] + 1, if X[i] == Y[j]
dp[i][j] = 0, if X[i] != Y[j]

乘积最大子序列

LC152 乘积最大子序列

因为负数的存在，前一步累计的最大值会变成最小值，前一步累计的最小值会变成最大值。因此需要维护两个dp数组。设max[i]为以nums[i]为结尾的子序列的最大乘积。min[i]为以nums[i]为结尾的子序列的最小乘积。

因此状态转移方程为：

min[i] = min(nums[i], max[i - 1] nums[i], min[i - 1] nums[i])
max[i] = max(nums[i], max[i - 1] nums[i], min[i - 1] nums[i])

code

class Solution {
public:
    int maxProduct(vector<int>& nums) {

        int res = INT_MIN;
        int dp_min = 1;
        int dp_max = 1;

        for(auto x : nums)
        {
            auto dp_min_temp = dp_min;
            dp_min = min({x, dp_max * x, dp_min * x});
            dp_max = max({x, dp_max * x, dp_min_temp * x});
            res = max(res, dp_max);
        }

        return res;

    }
};

最长字符串链

LC1048 Longest String Chain
不固定起点和终点的DAG最长路径问题。类似最长上升子序列，没有要求j < i。所以对原来的字符串数组按长度排序即可。

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& lhs, const string& rhs){return lhs.size() < rhs.size();});
        auto dp = vector<int>(words.size(), 0);
        for(int i = 0; i < words.size(); ++i){
            auto s = unordered_set<string>{};
            auto& word = words[i];
            for(int k = 0; k < word.size(); ++k){
                auto copy = word;
                copy.erase(copy.begin() + k);
                s.insert(copy);
            }
            for(int j = 0; j < i; ++j)
                if(s.find(words[j]) != s.end() && dp[i] < dp[j] ) dp[i] = dp[j];
            ++dp[i];
        }
        return *max_element(dp.begin(), dp.end());
    }
};

买卖股票

一个方法团列6道股票问题, Leetcode题解

设三个状态变量：第i天，交易了k次，是否持有股票。那么状态可以表示为dp[i,k,0]或dp[i,k,1]，即第i天交易了k次未持有股票时的最大收益和第i天交易了k次持有股票时的最大收益。

状态转移方程：

dp[i,k,0] = max(dp[i - 1, k, 0], dp[i - 1, k, 1] + price[i]) 今天我未持有股票—>前一天我未持有股票，今天我也没买或前一天我持有股票，今天我把他卖了。
dp[i,k,1] = max(dp[i - 1, k, 1], dp[i - 1, k - 1, 0] - price[i])
今天我持有股票—>前一天我未持有股票，今天我买了股票，交易次数增多了一次。或者我前一天就持有股票，今天继续持有。

初始状态：

dp[i,0,0] = 0 ：一次都没交易，也没持有股票，那么收益必然是0。
dp[i,0,1] = -inf ：一次都没交易，但是持有了股票，不允许的状态，设为-inf，让他必然被排除掉。
dp[-1,k,0] = 0 ：在一切发生之前，不管做了多少交易，与当前所求无关，设收益是0。
dp[-1,k,1] = -inf：在一切发生之前，不管做了多少交易，不能留着股票不卖，不允许的状态，设为-inf，让他必然被排除掉。

LC121 买卖股票的最佳时机
只允许买卖一次，即k必然为0或1。

状态转移方程：

dp[i,1,0] = max(dp[i - 1, 1, 0], dp[i - 1, 1, 1] + price[i]) ：该状态k必然为1，可以省去
dp[i,0,0] = max(dp[i - 1, 0, 0], dp[i - 1, 0, 1] + price[i]) ：该状态为初始状态，必然为0，不需要转移。
dp[i,1,1] = max(dp[i - 1, 1, 1], dp[i - 1, 0, 0] - price[i]) ：dp[i - 1, 0, 0]必然为0。
dp[i,0,1] = max(dp[i - 1, 0, 1], dp[i - 1, - 1, 0] - price[i]) ：不可能的状态，排除

因为所有k都为1，k=0的状态都为初始状态被隐去。所以状态转移方程可以化简为：

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i])
dp[i,1] = max(dp[i - 1, 1], - price[i])

初始状态为

dp[-1, 0] = 0, dp[-1,1] = -inf —> dp[0,0] = 0
dp[-1, 1] = -inf, -price[0] = -price[0] —> dp[0,1] = -price[0]

因为状态转移方程只和前一状态有关，因此只需两个变量即可完成迭代更新

dp_i0 = 0
dp_i1 = -price[0]

for i = 1 to N
    dp_i0 = max(dp_i0, dp_i1 + price[i])
    dp_i1 = max(dp_i1, -price[i])

最后所求为dp_i0。因为dp_i0必然大于等于dp_i1，因为手上持有的股票还没卖出去的收益肯定小于已经卖出去的收益。

code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;

        auto dp_i0 = 0;
        auto dp_i1 = -prices[0];
        

        for (auto it = ++prices.begin(); it != prices.end(); ++it)
        {
            dp_i0 = max(dp_i0, dp_i1 + *it);
            // notice that dp_i1 has no relationship with dp_i0, we do not need 
            // to make a copy of dp_i0.
            dp_i1 = max(dp_i1, -(*it));
        }

        return dp_i0;
    }
};

LC122 买卖股票的最佳时机II

对交易次数不设限制。

状态转移方程：

dp[i,k,0] = max(dp[i - 1, k, 0], dp[i - 1, k, 1] + price[i])
dp[i,k,1] = max(dp[i - 1, k, 1], dp[i - 1, k - 1, 0] - price[i])

由于对k不设限制，所以k这个维度已经失去意义。

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i])
dp[i,1] = max(dp[i - 1, 1], dp[i - 1, 0] - price[i])

初始状态

dp[0,0] = max(dp[- 1, 0], dp[- 1, 1] + price[0]) —> max(0, -inf + price[0]) = 0
dp[0,1] = max(dp[- 1, 1], dp[- 1, 0] - price[0]) —> max(-inf, 0 - price[0]) = -price[0]

由于状态只和前一状态有关

dp_i0 = 0
dp_i1 = -price[0]

for i = 1 to N
    tmp   = dp_i0
    dp_i0 = max(dp_i0, dp_i1 + price[i])
    dp_i1 = max(dp_i1, tmp - price[i])

code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        auto dp_i0 = 0;
        auto dp_i1 = -prices[0];

        for(auto it = ++prices.begin(); it != prices.end(); ++it)
        {
            auto dp_i0_tmp = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + *it);
            dp_i1 = max(dp_i1, dp_i0_tmp - (*it));
        }

        return dp_i0;
    }
};

LC122 买卖股票的最佳时机III

最多完成两笔交易。

状态转移方程：

dp[i,k,0] = max(dp[i - 1, k, 0], dp[i - 1, k, 1] + price[i])
dp[i,k,1] = max(dp[i - 1, k, 1], dp[i - 1, k - 1, 0] - price[i])

k = 0,1,2

初始状态

dp[-1,k,0] = 0
dp[-1,k,1] = -inf
dp[i,0,1] = -inf
dp[i,0,0] = 0

因为每个状态都和之前两个状态有关(k = 1,2)，所以需要两个长度为2的数组。而且要从后往前更新，否则会覆盖状态。

dp[i,0,1] = max(dp[i - 1, 0, 1], dp[i - 1, - 1, 0] - price[i]) —> dp[i - 1, - 1, 0] 为不允许的状态。
因此：
dp[i,0,1] = dp[i - 1, 0, 1]

for k = 1 to 2
    dp_i0[k] = 0
    dp_i1[k] = -inf

for i = 1 to N
    for k = 2 to 1
        dp_i0[k] = max(dp_i0[k], dp_i1[k] + price[i])
        dp_i1[k] = max(dp_i1[k], dp_i0[k - 1] - price[i])

返回的应该为dp_i0[]数组中的最大值。

code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        auto dp_i0 = array<int, 3>{};
        auto dp_i1 = array<int, 3>{};

        for(int k = 0; k <= 2; ++k)
        {
            dp_i0[k] = 0;
            dp_i1[k] = INT_MIN;
        }

        for(int i = 0; i < prices.size(); ++i)
        {
            for(int k = 2; k >= 1; --k)
            {
                dp_i0[k] = max(dp_i0[k], dp_i1[k] + prices[i]);
                dp_i1[k] = max(dp_i1[k], dp_i0[k - 1] - prices[i]);
            }
        }

        return *(max_element(dp_i0.begin(), dp_i0.end()));
    }
};

LC188 买卖股票的最佳时机IV

和前一题基本一致，只不过这次k成为了变量。麻烦的问题在于当k很大的时候，生成的数组会爆堆。因为一次交易（一买一卖）至少也需要两天(A股T+1？)。所以我们认为如果max_k > prices.size() / 2，k对整个问题就没有任何限制作用了。我们就可以用无限次的交易的函数来计算了。

code

class Solution {
public:
    int maxProfit(int max_k, vector<int>& prices) {
        if(prices.empty()) return 0;
        if(max_k> prices.size() / 2) return maxProfit_infk(prices);
        auto dp_i0 = vector<int>(max_k + 1, 0);
        auto dp_i1 = vector<int>(max_k + 1, 0);

        for(int k = 0; k <= max_k; ++k)
        {
            dp_i0[k] = 0;
            dp_i1[k] = INT_MIN;
        }

        for(int i = 0; i < prices.size(); ++i)
        {
            for(int k = max_k; k >= 1; --k)
            {
                dp_i0[k] = max(dp_i0[k], dp_i1[k] + prices[i]);
                dp_i1[k] = max(dp_i1[k], dp_i0[k - 1] - prices[i]);
            }
        }

        return *(max_element(dp_i0.begin(), dp_i0.end()));
    }

    int maxProfit_infk(vector<int>& prices) {
        if(prices.empty()) return 0;
        auto dp_i0 = 0;
        auto dp_i1 = -prices[0];

        for(auto it = ++prices.begin(); it != prices.end(); ++it)
        {
            auto dp_i0_tmp = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + *it);
            dp_i1 = max(dp_i1, dp_i0_tmp - (*it));
        }

        return dp_i0;
    }
};

LC309 最佳买卖股票时机含冷冻期

不限制交易次数，但是出现了冷冻期。
观察原来的状态转移方程

dp[i,k,0] = max(dp[i - 1, k, 0], dp[i - 1, k, 1] + price[i])
dp[i,k,1] = max(dp[i - 1, k, 1], dp[i - 1, k - 1, 0] - price[i])

不限制交易次数，k这个维度已经失去了意义

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i])
dp[i,1] = max(dp[i - 1, 1], dp[i - 1, 0] - price[i])

买入股票的时候，由于存在冷却期，所以不能从i - 1这个状态转移，要从i - 2转移。这个影响第一次购买股票，因为我们只需要设置到初始条件即可。

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i])
dp[i,1] = max(dp[i - 1, 1], dp[i - 2, 0] - price[i])

初始条件

dp[0,0] = max(dp[-1,0], dp[-1,1] + price[0]) —> max(0, -inf + price[0]) —> 0
dp[0,1] = max(dp[-1,1], dp[-2,0] - price[0]) —> max(-inf, 0 - price[0]) —> -price[0]

dp_i0仅和前一个状态相关。但是dp_i1和前两个状态相关。我们需要三个状态变量来记录。

dp_i0 = 0
dp_i0_pre = 0
dp_i1 = price[0]

for i = 0 to N
    dp_i0_copy = dp_i0
    dp_i0 = max(dp_i0, dp_i1 + prices[i])
    dp_i1 = max(dp_i1, dp_i0_pre - prices[i])
    dp_i0_pre = dp_i0_copy

code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;

        int dp_i0 = 0;
        int dp_i0_pre = 0;
        int dp_i1 = -prices[0];

        for(auto price : prices)
        {
            int dp_i0_copy = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + price);
            dp_i1 = max(dp_i1, dp_i0_pre - price);
            dp_i0_pre = dp_i0_copy;
        }

        return dp_i0;
    }
};

LC714 买卖股票的最佳时机含手续费

不限交易次数，状态转移方程

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i])
dp[i,1] = max(dp[i - 1, 1], dp[i - 1, 0] - price[i])

因为含有手续费，在卖出股票时（或者买入时），需要缴纳手续费（券商佣金+印花税？）。

dp[i,0] = max(dp[i - 1, 0], dp[i - 1, 1] + price[i] - fee)
dp[i,1] = max(dp[i - 1, 1], dp[i - 1, 0] - price[i])

初始状态

dp[0,0] = max(dp[- 1, 0], dp[-1, 1] + price[0] - fee) —> 0
dp[0,1] = max(dp[- 1, 1], dp[- 1, 0] - price[i]) —> -price[0]

dp_i0 = 0
dp_i1 = -price[0]

for i = 0 to N
    dp_i0_copy = dp_i0
    dp_i0 = max(dp_i0, dp_i1 + price[i] - fee)
    dp_i1 = max(dp_i1, dp_i0_copy - price[i])

code

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.empty()) return 0;
        
        int dp_i0 = 0;
        int dp_i1 = -prices[0];

        for(auto price : prices)
        {
            int dp_i0_copy = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + price - fee);
            dp_i1 = max(dp_i1, dp_i0_copy - price);
        }

        return dp_i0;
    }
};

矩阵中的路径

LC62 不同路径

状态转移方程
dp[i][j] = dp[i - 1][j] if j == 0
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
i的空间上只和前一状态有关，因此只需维持一个长度为m的数组即可。

code

class Solution {
public:
    int uniquePaths(int m, int n) {
        auto dp = vector<int>(m, 1);
        for(int i = 1; i < n; ++i)
        {
            for(int j = 1; j < m; ++j)
            {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp.back();
    }
};

LC63 不同路径II

可以用回溯法+hashmap记录已经遍历过的路径，速度也不差。

backtrack with hashmap code

template<typename T1, typename T2>
struct hash_pair
{
    hash<T1> hash_t1;
    hash<T2> hash_t2;
    size_t operator()(const pair<T1, T2>& pair) const
    {
        return hash_t1(pair.first) ^ hash_t2(pair.second);
    }
};

class Solution {
    int m;
    int n;
    unordered_map<pair<int, int>, int, hash_pair<int, int>> lookup_table;
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        m = obstacleGrid.size();
        n = obstacleGrid.front().size();
        if(m == 0 || n == 0) return 0;
        // if there is an obstable on the finish point or on the start point
        if(obstacleGrid.back().back() == 1 || obstacleGrid.front().front() == 1) 
            return 0;
        return backtrack(obstacleGrid, 0, 0);
    }

    int backtrack(const vector<vector<int>>& obstacleGrid, int x, int y)
    {
        // invalid path
        if(x >= m || y >= n || obstacleGrid[x][y] == 1) return 0;
        // arrived at the finish point
        if(x == m - 1 && y == n - 1) return 1;
        pair<int, int> moveLeft  = {x + 1, y};
        pair<int, int> moveRight = {x, y + 1}; 
        // move down and move right

        int left = lookup_table.count(moveLeft)      ? 
                    lookup_table[moveLeft]           : 
                    backtrack(obstacleGrid, x + 1, y);
        int right = lookup_table.count(moveRight)      ? 
                   lookup_table[moveRight]           : 
                   backtrack(obstacleGrid, x, y + 1);

        // put it into the hashmap
        lookup_table[{x, y}] = left + right;
        return left + right;
    }
};

LC64 最小路径和
定义状态dp[i][j]为从左上角走到i,j处的最小路径和。由于每个状态只能从其左边(i, j -1)或其上边(i - 1, j)转移。所以状态转移方程为：dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])。
注意：

边界判断问题。
size_t不能为负数的问题。

code

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty() || grid.front().empty()) return 0;

        auto row = grid.size();
        auto col = grid.front().size();

        auto dp = vector<vector<int>>(row, vector<int>(col, 0));

        for(size_t i = 0; i < row; ++i)
        {
            for(size_t j = 0; j < col; ++j)
            {
                if( (i == 0) && (j == 0) )
                {
                    dp[i][j] = grid[i][j];
                    continue;
                }
                
                if(i == 0)
                {
                    dp[i][j] = grid[i][j] + dp[i][j - 1];
                    continue;
                }

                if(j == 0)
                {
                    dp[i][j] = grid[i][j] + dp[i - 1][j];
                    continue;
                }
                
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp.back().back();
    }
};

背包问题

背包问题的通解形式

01背包

一个容量为$V$的背包和$N$件物品。将第$i$件物品放入背包的费用是$C_i$，获得的收益是$W_i$。每种物品只有一件。设前$i$件物品放入容量为$v$的背包中获得的最大价值为$F[i,v]$。

则状态转移方程为拿第$i$件物品后的价值和不拿第$i$件物品的最大值：
$F[i,v] = F[i - 1, v], F[i - 1, v - C_i] + W_i$
注意在$i$的维度上，每个状态仅跟上一个状态$i - 1$相关。因此我们可以采用一个数组F[v]就可以记录所有的状态。
为了不覆盖先前的状态，我们从底向上反向填表：

1
2
3

for i = 1 to N:
    for v = V to C_i:
        F[v] = max(F[v], F[v - Ci] + Wi)

初始化问题：

如果要保证背包填满，将F[0]初始化为0，其他初始化为负无穷大。
如果不需要保证背包填满，将所有初始化为0即可。

完全背包

一个容量为$V$的背包和$N$件物品。将第$i$件物品放入背包的费用是$C_i$，获得的收益是$W_i$。每种物品有无数件。设前$i$件物品放入容量为$v$的背包中获得的最大价值为$F[i,v]$。

只需将01背包的填表顺序反过来，即从$C_i$到$V$填表：

1
2
3

for i = 1 to N:
    for v = C_i to V:
        F[v] = max(F[v], F[v - Ci] + Wi)

求填满背包的最少物品数量

将初始化值变为F[0] = 0，其他初始化为F[i] = INT_MAX。之后将状态转移方程换成min，并且所有物品的价值设置成Wi = 1。

求装满背包解的数目

将初始化值变为F[0] = 1，其他初始化为F[i] = 0。状态转移方程变为sum。物品价值无用，设置为0。

01背包题目

LC494 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

思路：

默认所有数字前面都是正号，将所有数字加起来得到一个和sum
如果sum比S小，因为数组中的都是非负整数，那么无论我们给哪个数加符号，都会使得sum更小。所以无解。
如果sum == S，首先如果一个符号都不动是一个解决。要产生其他的解，那我们只能改0前面的符号。找找数组中有几个零，这些零前面正负号的组合共有$2^n$种。没有零的话，就是一种$2^0$。所以返回$2^n$
如果sum > S，我们看看sum和S的差是不是能被2整除，如果不能被2整除，无解。
如果sum > S且能被2整除，问题转换为01背包问题，求解装满背包的解的数量。

code

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        auto sum = accumulate(nums.begin(), nums.end(), 0);
        
        // a_i >= 0, change sign will only make sum even smaller
        if (sum < S) return 0;
        // a_i >= 0, we can only change the signs of zeros
        // there are 2^(num_of_zeros) possible solutions
        if (sum == S)
        {
            auto num_of_zeros = count(nums.begin(), nums.end(), 0);
            return 1 << num_of_zeros;
        }
        // sum > S
        // change a_i will decrease S by 2 * a_i, which indicates that
        // (sum - S) mod 2 == 0, otherwise there will be no solution
        if ((sum - S) % 2 != 0) return 0;
        // all a_i that change its sign must accumulate to (sum - S) / 2
        sum = (sum - S) / 2;
        // we could use each number exactly one time
        // this is a 0-1 knapsack problem.
        auto dp = vector<int>(sum + 1, 0);
        dp[0] = 1;
        // item's cost is the number nums[i]
        // volume is the sum
        for(int i = 0; i < nums.size(); ++i)
        {
            
            for(int j = sum; j >= nums[i]; --j)
            {
                
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
};

完全背包

完全平方数

LC279 完全平方数

完全背包。要求填满背包。统计最少物品个数。

思路：

正向遍历数组
初始化数组除了dp[0]=0，其他全为INT_MAX
max改为min

code

class Solution {
public:
    int numSquares(int n) {
        auto dp = vector<int>(n + 1, INT_MAX);
        dp[0] = 0;
        // there are floor(sqrt(n)) possible items.
        // the cost of item i is i * i
        // the value of every item is -1
        auto last_item = static_cast<int>(sqrt(n));
        for(int i = 1; i <= last_item; ++i)
        {
            for(int j = i * i; j < n + 1; ++j)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp.back();
    } 
};

换硬币

LC322 Coin Change
思路一：
指定起点和终点的最优路径长度问题：将剩余钱数$P$看作顶点，如果$P - coins[i] \geq 0$则存在边$(P, P-coins[i])$。求$\mathrm{path}(P, 0)$的最小长度。如果不存在$\mathrm{path}(P, 0)$，则返回-1。
基本情况

$P_0 = 0$

递归表达式

$P_i = \min\{P_{(i - \text{coins}[j])} | i - \text{coins}[j] \geq 0\} + 1$

为了处理换不成的问题，将dp数组都初始化为一个不能达到的大值amount + 1。这样对于不存在的路径，经过循环后其值会被更新为amount + 2。其他路径如果使用不可能达到的路径作为子问题的路径，最小也会超过amount。如果有解，则会使用较小的值。所以在最后判断dp[amount] > amount即可。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        auto dp = vector<int>(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i){
            for(auto coin : coins)
                if(i >= coin && dp[i] > dp[i - coin])
                    dp[i] = dp[i - coin];
            ++dp[i];
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

思路二：
这是一个完全背包问题，要求必须将背包正好装满。按《背包九讲》中把dp[0]初始化为0，其他为$\infty$即可。注意这里不可以用$INT_MAX$，因为INT_MAX上面再做加法会溢出，所以要用一个不可能取得到的大数，比如amount + 1。

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

换硬币解的个数

LC518 Coin Change 2

完全背包问题，求可行解的个数，只需将完全背包中的max换成sum，令dp[0] = 1即可。

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

钢条切割

CLRS动态规划的例题。
思路一：
指定起点和终点的最大权路径问题。顶点$P$和$P-1, \cdots, P-i, \cdots, 0$之间都有边，边的权重为$price(i)$。寻找路径$\text{path}(P, 0)$的加权最大值。

递归表达式

$\left\{ \begin{align}&P_0 = 0\\&P_n = \max_{1 \leq i \leq n}(P_i + P_{n - i}) \end{align}\right.$

思路二：要求背包恰好装满的完全背包问题。

class rodCut{
public:
    rodCut()
    :memo{}
    ,cut{}
    {memo.fill(INT_MIN);memo[0] = 0;memo[1] = 1;cut.fill(INT_MIN);}
    int top_down_naive(int length){
        if(length == 0) return 0;
        int q = INT_MIN;
        for(int i = 1; i <= length; ++i)
           q = max(q, price[i] + top_down_naive(length - i));

        return q;
    }

    int top_down_memoized(int length){
        if(memo[length] < 0) {
            int q = INT_MIN;
            for (int i = 1; i <= length; ++i)
                q = max(q, price[i] + top_down_memoized(length - i));
            memo[length] = q;
        }
        return memo[length];
    }

    int bottom_up(int length){
        if(memo[length] < 0){
            for(int j = 3; j <= length; ++j)
                for(int i = 1; i <= j; ++i)
                    if(auto q = price[i] + memo[j - i]; memo[j] < q){
                        memo[j] = q;
                        cut[j] = i;
                    }
        }
        return memo[length];
    }

    vector<int> solution(int length){
        if(length == 0 || memo[length] < 0) return {};
        auto sol = vector<int>{};
        while(length > 0){
            sol.push_back(cut[length]);
            length -= cut[length];
        }
        return sol;
    }
private:
    constexpr static array<int, 11> price
    = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    array<int, 11> memo;
    array<int, 11> cut;
};

二维费用的背包问题

LC474 Ones and Zeroes
典型的《背包九讲》中二维费用的01背包问题。每种物品都有两个代价，c是该物品1的个数，d是该物品0的个数。m，n则是你这两种背包的容量。用一个二维数组dp[v][u]按照01背包的思路，反向做内层循环即可解决。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        if(strs.empty()) return 0;
        auto nStr = strs.size();
        auto c = vector<int>(nStr);
        auto d = vector<int>(nStr);
        for(int i = 0; i < nStr; ++i)
            for(auto ch : strs[i]){
                if(ch == '0') ++c[i];
                else ++d[i];
            }
        
        auto dp = vector<vector<int> >(m + 1);
        for(auto& vec : dp) vec.resize(n + 1, 0);
        
        for(size_t i = 0; i < nStr; ++i)
            for(int v = m; v >= c[i]; --v)
                for(int u = n; u >= d[i]; --u)
                    dp[v][u] = max(dp[v][u], dp[v - c[i]][u - d[i]] + 1);
                                    
        return dp[m][n];
    }
};

最大正方形

LC221 最大正方形

如果一个点是1

以他为右下角，能形成的最小正方形边长为1。
以他为右下角，能形成的最大正方形长取决于这三个当中的最小值 + 1
- 以他上方的点为右下角，能形成的正方形边长
- 以他左上方的点为右下角，能形成的正方形边长
- 以他左边的点为右下角，能形成的正方形边长
  状态转移方程：
  如果matrix[i][j] == '1'，dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1
  如果matrix[i][j] == '0'，dp[i][j] = 0
  初始状态dp[0][0] = matrix[0][0] - '0'

注意：

处理i和j的下标溢出问题很麻烦。不如我们给dp矩阵左边和上边增加一行0。

code

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix.front().empty()) return 0;
        auto row = matrix.size();
        auto col = matrix.front().size();

        // create a dp matrix
        // add a row and a col to avoid underflow 
        auto dp = vector<vector<int>>(row + 1, vector<int>(col + 1, 0));
        auto res = 0;
        for(size_t i = 1; i < row + 1; ++i)
        {
            for(size_t j = 1; j < col + 1; ++j)
            {
                if(matrix[i - 1][j - 1] == '0') dp[i][j] = 0;
                else
                {
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
};

打家劫舍

LC337 打家劫舍III

思路一：

记录当前node是否被劫掠，并传给一个bool给递归调用的子node
如果该节点的双亲节点被劫掠，那么这个节点不可以被劫掠。
如果该节点的双亲节点没被劫掠，那么这个节点可以被劫掠，也可以不被劫掠。

最后一个case TLE，估计是函数调用太多了。

TLE code

class Solution {
public:
    int rob(TreeNode* root) {
        return max(rob(root, true), rob(root, false));
    }

    int rob(TreeNode* root, bool isParentRobbed)
    {
        // you rob void, you get void
        if(!root) return 0;

        // if its parent is robbed, we cannot rob this node
        if(isParentRobbed)
        {
            return rob(root->left, false) 
                 + rob(root->right, false);
        }

        // else, its parent is not robbed, free to rob this node
        {
            auto robbed = root->val + rob(root->left, true)
                       +rob(root->right, true);
            auto not_robbed =  rob(root->left, false)
                            +rob(root->right, false);

            return max(robbed, not_robbed);
        }
    }
};

思路二：

不需要告诉子node自己是否被劫掠，而是每次都返回两个值，一个是被劫掠的收益，另一个是不被劫掠的收益。
被劫掠的收益 = 当前节点的值 + 不劫掠左孩子 + 不劫掠右孩子
不被劫掠的收益 = max(劫掠左 + 劫掠右, 不劫掠左 + 劫掠右，劫掠左 + 不劫掠右，不劫掠左 + 不劫掠右)

减少了非常多的函数调用开始，可以超过近97%的解

code

class Solution {
public:
    int rob(TreeNode* root) {
        auto [r,nr] = rob_(root);
        return max(r, nr);
    }

    pair<int, int> rob_(TreeNode* root)
    {
        // you cannot rob void
        if(!root) return {0, 0};

        auto [l_robbed, l_not_robbed] = rob_(root->left);
        auto [r_robbed, r_not_robbed] = rob_(root->right);

        return {
            // this node is robbed
            root->val + l_not_robbed + r_not_robbed,
            // this node is not robbed
                max({l_robbed + r_robbed, 
                     l_not_robbed + r_not_robbed,
                     l_not_robbed + r_robbed,
                     l_robbed + r_not_robbed})};
    }
};