chapDynamicProgramming.tex

\chapter{动态规划}


\section{Triangle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:triangle}


\subsubsection{描述}
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
\begin{Code}
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
\end{Code}
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only $O(n)$ extra space, where n is the total number of rows in the triangle.


\subsubsection{分析}
设状态为$f(i, j)$，表示从从位置$(i,j)$出发，路径的最小和，则状态转移方程为
$$
f(i,j)=\min\left\{f(i,j+1),f(i+1,j+1)\right\}+(i,j)
$$


\subsubsection{代码}
\begin{Code}
// LeetCode, Triangle
// 时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
    int minimumTotal (vector<vector<int>>& triangle) {
        for (int i = triangle.size() - 2; i >= 0; --i)
            for (int j = 0; j < i + 1; ++j)
                triangle[i][j] += min(triangle[i + 1][j],
                        triangle[i + 1][j + 1]);

        return triangle [0][0];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Maximum Subarray} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:maximum-subarray}


\subsubsection{描述}
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array \code{[−2,1,−3,4,−1,2,1,−5,4]},
the contiguous subarray \code{[4,−1,2,1]} has the largest \code{sum = 6}.


\subsubsection{分析}
最大连续子序列和，非常经典的题。

当我们从头到尾遍历这个数组的时候，对于数组里的一个整数，它有几种选择呢？它只有两种选择： 1、加入之前的SubArray；2. 自己另起一个SubArray。那什么时候会出现这两种情况呢？

如果之前SubArray的总体和大于0的话，我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的SubArray

如果之前SubArray的总体和为0或者小于0的话，我们认为其对后续结果是没有贡献，甚至是有害的（小于0时）。这种情况下我们选择以这个数字开始，另起一个SubArray。

设状态为\fn{f[j]}，表示以\fn{S[j]}结尾的最大连续子序列和，则状态转移方程如下：
\begin{eqnarray}
f[j] &=& \max\left\{f[j-1]+S[j],S[j]\right\}, \text{ 其中 }1 \leq j \leq n \nonumber \\
target &=& \max\left\{f[j]\right\}, \text{ 其中 }1 \leq j \leq n \nonumber
\end{eqnarray}

解释如下：
\begindot
\item 情况一，S[j]不独立，与前面的某些数组成一个连续子序列，则最大连续子序列和为$f[j-1]+S[j]$。
\item 情况二，S[j]独立划分成为一段，即连续子序列仅包含一个数S[j]，则最大连续子序列和为$S[j]$。
\myenddot  

其他思路：
\begindot
\item 思路2：直接在i到j之间暴力枚举，复杂度是$O(n^3)$
\item 思路3：处理后枚举，连续子序列的和等于两个前缀和之差，复杂度$O(n^2)$。
\item 思路4：分治法，把序列分为两段，分别求最大连续子序列和，然后归并，复杂度$O(n\log n)$
\item 思路5：把思路2$O(n^2)$的代码稍作处理，得到$O(n)$的算法
\item 思路6：当成M=1的最大M子段和
\myenddot


\subsubsection{动规}
\begin{Code}
// LeetCode, Maximum Subarray
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int maxSubArray(int A[], int n) {
        int result = INT_MIN, f = 0;
        for (int i = 0; i < n; ++i) {
            f = max(f + A[i], A[i]);
            result = max(result, f);
        }
        return result;
    }
};
\end{Code}


\subsubsection{思路5}
\begin{Code}
// LeetCode, Maximum Subarray
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    int maxSubArray(int A[], int n) {
        return mcss(A, n);
    }
private:
    // 思路5，求最大连续子序列和
    static int mcss(int A[], int n) {
        int i, result, cur_min;
        int *sum = new int[n + 1];  // 前n项和

        sum[0] = 0;
        result = INT_MIN;
        cur_min = sum[0];
        for (i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + A[i - 1];
        }
        for (i = 1; i <= n; i++) {
            result = max(result, sum[i] - cur_min);
            cur_min = min(cur_min, sum[i]);
        }
        delete[] sum;
        return result;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Binary Tree Maximum Path Sum，见 \S \ref{sec:binary-tree-maximum-path-sum}
\myenddot


\section{Palindrome Partitioning II} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:palindrome-partitioning-ii}


\subsubsection{描述}
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given \code{s = "aab"},

Return 1 since the palindrome partitioning \code{["aa","b"]} could be produced using 1 cut.


\subsubsection{分析}
定义状态\fn{f(i,j)}表示区间\fn{[i,j]}之间最小的cut数，则状态转移方程为 
$$
f(i,j)=\min\left\{f(i,k)+f(k+1,j)\right\}, i \leq k \leq j, 0 \leq i \leq j<n
$$
这是一个二维函数，实际写代码比较麻烦。
 
所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为\code{f(i)=区间[i, n-1]之间最小的cut数}，n为字符串长度，则状态转移方程为
$$
f(i)=\min\left\{f(j+1)+1\right\}, i \leq j<n
$$

一个问题出现了，就是如何判断\fn{[i,j]}是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。

定义状态\fn{P[i][j] = true if [i,j]为回文}，那么
\begin{Code}
P[i][j] = str[i] == str[j] && P[i+1][j-1]
\end{Code}


\subsubsection{代码}
\begin{Code}
// LeetCode, Palindrome Partitioning II
// 时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
    int minCut(string s) {
        const int n = s.size();
        int f[n+1];
        bool p[n][n];
        fill_n(&p[0][0], n * n, false);
        //the worst case is cutting by each char
        for (int i = 0; i <= n; i++)
            f[i] = n - 1 - i; // 最后一个f[n]=-1
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    f[i] = min(f[i], f[j + 1] + 1);
                }
            }
        }
        return f[0];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Palindrome Partitioning，见 \S \ref{sec:palindrome-partitioning}
\myenddot


\section{Maximal Rectangle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:maximal-rectangle}


\subsubsection{描述}
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
// LeetCode, Maximal Rectangle
// 时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty())  return 0;

        const int m = matrix.size();
        const int n = matrix[0].size();
        vector<int> H(n, 0);
        vector<int> L(n, 0);
        vector<int> R(n, n);

        int ret = 0;
        for (int i = 0; i < m; ++i) {
            int left = 0, right = n;
            // calculate L(i, j) from left to right
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++H[j];
                    L[j] = max(L[j], left);
                } else {
                    left = j+1;
                    H[j] = 0; L[j] = 0; R[j] = n;
                }
            }
            // calculate R(i, j) from right to left
            for (int j = n-1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j]*(R[j]-L[j]));
                } else {
                    right = j;
                }
            }
        }
        return ret;
    }
};
\end{Code}


\subsubsection{相关题目}

\begindot
\item 无
\myenddot


\section{Best Time to Buy and Sell Stock III} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:best-time-to-buy-and-sell-stock-iii}


\subsubsection{描述}
Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


\subsubsection{分析}
设状态$f(i)$，表示区间$[0,i](0 \leq i \leq n-1)$的最大利润，状态$g(i)$，表示区间$[i, n-1](0 \leq i \leq n-1)$的最大利润，则最终答案为$\max\left\{f(i)+g(i)\right\},0 \leq i \leq n-1$。

允许在一天内买进又卖出，相当于不交易，因为题目的规定是最多两次，而不是一定要两次。

将原数组变成差分数组，本题也可以看做是最大$m$子段和，$m=2$，参考代码：\myurl{https://gist.github.com/soulmachine/5906637}

\subsubsection{代码}
\begin{Code}
// LeetCode, Best Time to Buy and Sell Stock III
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;

        const int n = prices.size();
        vector<int> f(n, 0);
        vector<int> g(n, 0);

        for (int i = 1, valley = prices[0]; i < n; ++i) {
            valley = min(valley, prices[i]);
            f[i] = max(f[i - 1], prices[i] - valley);
        }

        for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
            peak = max(peak, prices[i]);
            g[i] = max(g[i], peak - prices[i]);
        }

        int max_profit = 0;
        for (int i = 0; i < n; ++i)
            max_profit = max(max_profit, f[i] + g[i]);

        return max_profit;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Best Time to Buy and Sell Stock，见 \S \ref{sec:best-time-to-buy-and-sell-stock}
\item Best Time to Buy and Sell Stock II，见 \S \ref{sec:best-time-to-buy-and-sell-stock-ii}
\myenddot


\section{Interleaving String} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:interleaving-string}


\subsubsection{描述}
Given $s1, s2, s3$, find whether $s3$ is formed by the interleaving of $s1$ and $s2$.

For example, Given: \code{s1 = "aabcc", s2 = "dbbca"},

When \code{s3 = "aadbbcbcac"}, return true.

When \code{s3 = "aadbbbaccc"}, return false.


\subsubsection{分析}
设状态\fn{f[i][j]}，表示\fn{s1[0,i]}和\fn{s2[0,j]}，匹配\fn{s3[0, i+j]}。如果s1的最后一个字符等于s3的最后一个字符，则\fn{f[i][j]=f[i-1][j]}；如果s2的最后一个字符等于s3的最后一个字符，则\fn{f[i][j]=f[i][j-1]}。因此状态转移方程如下：
\begin{Code}
f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
       || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);
\end{Code}


\subsubsection{递归}
\begin{Code}
// LeetCode, Interleaving String
// 递归，会超时，仅用来帮助理解
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.length() != s1.length() + s2.length())
            return false;

        return isInterleave(begin(s1), end(s1), begin(s2), end(s2),
                begin(s3), end(s3));
    }

    template<typename InIt>
    bool isInterleave(InIt first1, InIt last1, InIt first2, InIt last2,
            InIt first3, InIt last3) {
        if (first3 == last3)
            return first1 == last1 && first2 == last2;

        return (*first1 == *first3
                && isInterleave(next(first1), last1, first2, last2,
                        next(first3), last3))
                || (*first2 == *first3
                        && isInterleave(first1, last1, next(first2), last2,
                                next(first3), last3));
    }
};
\end{Code}


\subsubsection{动规}
\begin{Code}
// LeetCode, Interleaving String
// 二维动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.length() != s1.length() + s2.length())
            return false;

        vector<vector<bool>> f(s1.length() + 1,
                vector<bool>(s2.length() + 1, true));

        for (size_t i = 1; i <= s1.length(); ++i)
            f[i][0] = f[i - 1][0] && s1[i - 1] == s3[i - 1];

        for (size_t i = 1; i <= s2.length(); ++i)
            f[0][i] = f[0][i - 1] && s2[i - 1] == s3[i - 1];

        for (size_t i = 1; i <= s1.length(); ++i)
            for (size_t j = 1; j <= s2.length(); ++j)
                f[i][j] = (s1[i - 1] == s3[i + j - 1] && f[i - 1][j])
                        || (s2[j - 1] == s3[i + j - 1] && f[i][j - 1]);

        return f[s1.length()][s2.length()];
    }
};
\end{Code}


\subsubsection{动规+滚动数组}
\begin{Code}
// LeetCode, Interleaving String
// 二维动规+滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.length() + s2.length() != s3.length())
            return false;

        if (s1.length() < s2.length())
            return isInterleave(s2, s1, s3);

        vector<bool> f(s2.length() + 1, true);

        for (size_t i = 1; i <= s2.length(); ++i)
            f[i] = s2[i - 1] == s3[i - 1] && f[i - 1];

        for (size_t i = 1; i <= s1.length(); ++i) {
            f[0] = s1[i - 1] == s3[i - 1] && f[0];

            for (size_t j = 1; j <= s2.length(); ++j)
                f[j] = (s1[i - 1] == s3[i + j - 1] && f[j])
                        || (s2[j - 1] == s3[i + j - 1] && f[j - 1]);
        }

        return f[s2.length()];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Scramble String} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:scramble-string}


\subsubsection{描述}
Given a string $s1$, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of \code{s1 = "great"}:
\begin{Code}
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
\end{Code}

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node \code{"gr"} and swap its two children, it produces a scrambled string \code{"rgeat"}.
\begin{Code}
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
\end{Code}

We say that \code{"rgeat"} is a scrambled string of \code{"great"}.

Similarly, if we continue to swap the children of nodes \code{"eat"} and \code{"at"}, it produces a scrambled string \code{"rgtae"}.
\begin{Code}
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
\end{Code}

We say that \code{"rgtae"} is a scrambled string of \code{"great"}.

Given two strings $s1$ and $s2$ of the same length, determine if $s2$ is a scrambled string of $s1$.


\subsubsection{分析}
首先想到的是递归（即深搜），对两个string进行分割，然后比较四对字符串。代码虽然简单，但是复杂度比较高。有两种加速策略，一种是剪枝，提前返回；一种是加缓存，缓存中间结果，即memorization（翻译为记忆化搜索）。

剪枝可以五花八门，要充分观察，充分利用信息，找到能让节点提前返回的条件。例如，判断两个字符串是否互为scamble，至少要求每个字符在两个字符串中出现的次数要相等，如果不相等则返回false。

加缓存，可以用数组或HashMap。本题维数较高，用HashMap，\fn{map}和\fn{unordered_map}均可。

既然可以用记忆化搜索，这题也一定可以用动规。设状态为\fn{f[n][i][j]}，表示长度为$n$，起点为\fn{s1[i]}和起点为\fn{s2[j]}两个字符串是否互为scramble，则状态转移方程为
\begin{Code}
f[n][i][j]} =  (f[k][i][j] && f[n-k][i+k][j+k]) 
            || (f[k][i][j+n-k] && f[n-k][i+k][j])
\end{Code}


\subsubsection{递归}

\begin{Code}
// LeetCode, Interleaving String
// 递归，会超时，仅用来帮助理解
// 时间复杂度O(n^6)，空间复杂度O(1)
class Solution {
public:
    bool isScramble(string s1, string s2) {
        return isScramble(s1.begin(), s1.end(), s2.begin());
    }
private:
    typedef string::iterator Iterator;
    bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
        auto length = distance(first1, last1);
        auto last2 = next(first2, length);

        if (length == 1) return *first1 == *first2;

        for (int i = 1; i < length; ++i)
            if ((isScramble(first1, first1 + i, first2)
                 && isScramble(first1 + i, last1, first2 + i))
                    || (isScramble(first1, first1 + i, last2 - i)
                            && isScramble(first1 + i, last1, first2)))
                return true;

        return false;
    }
};
\end{Code}


\subsubsection{动规}
\begin{Code}
// LeetCode, Interleaving String
// 动规，时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
    bool isScramble(string s1, string s2) {
        const int N = s1.size();
        if (N != s2.size()) return false;

        // f[n][i][j]，表示长度为n，起点为s1[i]和
        // 起点为s2[j]两个字符串是否互为scramble
        bool f[N + 1][N][N];
        fill_n(&f[0][0][0], (N + 1) * N * N, false);

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                f[1][i][j] = s1[i] == s2[j];

        for (int n = 1; n <= N; ++n) {
            for (int i = 0; i + n <= N; ++i) {
                for (int j = 0; j + n <= N; ++j) {
                    for (int k = 1; k < n; ++k) {
                        if ((f[k][i][j] && f[n - k][i + k][j + k]) ||
                                (f[k][i][j + n - k] && f[n - k][i + k][j])) {
                            f[n][i][j] = true;
                            break;
                        }
                    }
                }
            }
        }
        return f[N][0][0];
    }
};
\end{Code}


\subsubsection{递归+剪枝}
\begin{Code}
// LeetCode, Interleaving String
// 递归+剪枝
// 时间复杂度O(n^6)，空间复杂度O(1)
class Solution {
public:
    bool isScramble(string s1, string s2) {
        return isScramble(s1.begin(), s1.end(), s2.begin());
    }
private:
    typedef string::iterator Iterator;
    bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
        auto length = distance(first1, last1);
        auto last2 = next(first2, length);
        if (length == 1) return *first1 == *first2;

        // 剪枝，提前返回
        int A[26]; // 每个字符的计数器
        fill(A, A + 26, 0);
        for(int i = 0; i < length; i++) A[*(first1+i)-'a']++;
        for(int i = 0; i < length; i++) A[*(first2+i)-'a']--;
        for(int i = 0; i < 26; i++) if (A[i] != 0) return false;

        for (int i = 1; i < length; ++i)
            if ((isScramble(first1, first1 + i, first2)
                 && isScramble(first1 + i, last1, first2 + i))
                    || (isScramble(first1, first1 + i, last2 - i)
                            && isScramble(first1 + i, last1, first2)))
                return true;

        return false;
    }
};
\end{Code}


\subsubsection{备忘录法}
\begin{Code}
// LeetCode, Interleaving String
// 递归+map做cache
// 时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
    bool isScramble(string s1, string s2) {
        cache.clear();
        return isScramble(s1.begin(), s1.end(), s2.begin());
    }
private:
    typedef string::const_iterator Iterator;
    map<tuple<Iterator, Iterator, Iterator>, bool> cache;

    bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
        auto length = distance(first1, last1);
        auto last2 = next(first2, length);

        if (length == 1) return *first1 == *first2;

        for (int i = 1; i < length; ++i)
            if ((getOrUpdate(first1, first1 + i, first2)
                    && getOrUpdate(first1 + i, last1, first2 + i))
                    || (getOrUpdate(first1, first1 + i, last2 - i)
                            && getOrUpdate(first1 + i, last1, first2)))
                return true;

        return false;
    }

    bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
        auto key = make_tuple(first1, last1, first2);
        auto pos = cache.find(key);

        return (pos != cache.end()) ?
                pos->second : (cache[key] = isScramble(first1, last1, first2));
    }
};
\end{Code}


\subsubsection{备忘录法}
\begin{Code}
typedef string::const_iterator Iterator;
typedef tuple<Iterator, Iterator, Iterator> Key;
// 定制一个哈希函数
namespace std {
template<> struct hash<Key> {
    size_t operator()(const Key & x) const {
        Iterator first1, last1, first2;
        tie(first1, last1, first2) = x;

        int result = *first1;
        result = result * 31 + *last1;
        result = result * 31 + *first2;
        result = result * 31 + *(next(first2, distance(first1, last1)-1));
        return result;
    }
};
}

// LeetCode, Interleaving String
// 递归+unordered_map做cache，比map快
// 时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
    unordered_map<Key, bool> cache;

    bool isScramble(string s1, string s2) {
        cache.clear();
        return isScramble(s1.begin(), s1.end(), s2.begin());
    }

    bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
        auto length = distance(first1, last1);
        auto last2 = next(first2, length);

        if (length == 1)
            return *first1 == *first2;

        for (int i = 1; i < length; ++i)
            if ((getOrUpdate(first1, first1 + i, first2)
                    && getOrUpdate(first1 + i, last1, first2 + i))
                    || (getOrUpdate(first1, first1 + i, last2 - i)
                            && getOrUpdate(first1 + i, last1, first2)))
                return true;

        return false;
    }

    bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
        auto key = make_tuple(first1, last1, first2);
        auto pos = cache.find(key);

        return (pos != cache.end()) ?
                pos->second : (cache[key] = isScramble(first1, last1, first2));
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Minimum Path Sum} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:minimum-path-sum}


\subsubsection{描述}
Given a $m \times n$ grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time


\subsubsection{分析}
跟 Unique Paths (见 \S \ref{sec:unique-paths}) 很类似。

设状态为\fn{f[i][j]}，表示从起点$(0,0)$到达$(i,j)$的最小路径和，则状态转移方程为：
\begin{Code}
f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j]
\end{Code}


\subsubsection{备忘录法}
\begin{Code}
// LeetCode, Minimum Path Sum
// 备忘录法
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        const int m = grid.size();
        const int n = grid[0].size();
        this->f = vector<vector<int> >(m, vector<int>(n, -1));
        return dfs(grid, m-1, n-1);
    }
private:
    vector<vector<int> > f;  // 缓存

    int dfs(const vector<vector<int> > &grid, int x, int y) {
        if (x < 0 || y < 0) return INT_MAX; // 越界，终止条件，注意，不是0

        if (x == 0 && y == 0) return grid[0][0]; // 回到起点，收敛条件

        return min(getOrUpdate(grid, x - 1, y),
                getOrUpdate(grid, x, y - 1)) + grid[x][y];
    }

    int getOrUpdate(const vector<vector<int> > &grid, int x, int y) {
        if (x < 0 || y < 0) return INT_MAX; // 越界，注意，不是0
        if (f[x][y] >= 0) return f[x][y];
        else return f[x][y] = dfs(grid, x, y);
    }
};
\end{Code}


\subsubsection{动规}
\begin{Code}
// LeetCode, Minimum Path Sum
// 二维动规
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        if (grid.size() == 0) return 0;
        const int m = grid.size();
        const int n = grid[0].size();

        int f[m][n];
        f[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            f[0][i] = f[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
};
\end{Code}


\subsubsection{动规+滚动数组}
\begin{Code}
// LeetCode, Minimum Path Sum
// 二维动规+滚动数组
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        const int m = grid.size();
        const int n = grid[0].size();

        int f[n];
        fill(f, f+n, INT_MAX); // 初始值是 INT_MAX，因为后面用了min函数。
        f[0] = 0;

        for (int i = 0; i < m; i++) {
            f[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                // 左边的f[j]，表示更新后的f[j]，与公式中的f[i[[j]对应
                // 右边的f[j]，表示老的f[j]，与公式中的f[i-1][j]对应
                f[j] = min(f[j - 1], f[j]) + grid[i][j];
            }
        }
        return f[n - 1];
    }
};
\end{Code}

\subsubsection{相关题目}
\begindot
\item Unique Paths, 见 \S \ref{sec:unique-paths}
\item Unique Paths II, 见 \S \ref{sec:unique-paths-ii}
\myenddot


\section{Edit Distance} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:edit-distance}


\subsubsection{描述}
Given two words \fn{word1} and \fn{word2}, find the minimum number of steps required to convert \fn{word1} to \fn{word2}. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:
\begindot
\item Insert a character
\item Delete a character
\item Replace a character
\myenddot


\subsubsection{分析}
设状态为\fn{f[i][j]}，表示\fn{A[0,i]}和\fn{B[0,j]}之间的最小编辑距离。设\fn{A[0,i]}的形式是\fn{str1c}，\fn{B[0,j]}的形式是\fn{str2d}，
\begin{enumerate}
\item 如果\fn{c==d}，则\fn{f[i][j]=f[i-1][j-1]}；
\item 如果\fn{c!=d}，
    \begin{enumerate}
        \item 如果将c替换成d，则\fn{f[i][j]=f[i-1][j-1]+1}；
        \item 如果在c后面添加一个d，则\fn{f[i][j]=f[i][j-1]+1}；
        \item 如果将c删除，则\fn{f[i][j]=f[i-1][j]+1}；
    \end{enumerate}
\end{enumerate}


\subsubsection{动规}
\begin{Code}
// LeetCode, Edit Distance
// 二维动规，时间复杂度O(n*m)，空间复杂度O(n*m)
class Solution {
public:
    int minDistance(const string &word1, const string &word2) {
        const size_t n = word1.size();
        const size_t m = word2.size();
        // 长度为n的字符串，有n+1个隔板
        int f[n + 1][m + 1];
        for (size_t i = 0; i <= n; i++)
            f[i][0] = i;
        for (size_t j = 0; j <= m; j++)
            f[0][j] = j;

        for (size_t i = 1; i <= n; i++) {
            for (size_t j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else {
                    int mn = min(f[i - 1][j], f[i][j - 1]);
                    f[i][j] = 1 + min(f[i - 1][j - 1], mn);
                }
            }
        }
        return f[n][m];
    }
};
\end{Code}


\subsubsection{动规+滚动数组}
\begin{Code}
// LeetCode, Edit Distance
// 二维动规+滚动数组
// 时间复杂度O(n*m)，空间复杂度O(n)
class Solution {
public:
    int minDistance(const string &word1, const string &word2) {
        if (word1.length() < word2.length())
            return minDistance(word2, word1);

        int f[word2.length() + 1];
        int upper_left = 0; // 额外用一个变量记录f[i-1][j-1]

        for (size_t i = 0; i <= word2.size(); ++i)
            f[i] = i;

        for (size_t i = 1; i <= word1.size(); ++i) {
            upper_left = f[0];
            f[0] = i;

            for (size_t j = 1; j <= word2.size(); ++j) {
                int upper = f[j];

                if (word1[i - 1] == word2[j - 1])
                    f[j] = upper_left;
                else
                    f[j] = 1 + min(upper_left, min(f[j], f[j - 1]));

                upper_left = upper;
            }
        }

        return f[word2.length()];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Decode Ways} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:decode-ways}


\subsubsection{描述}
A message containing letters from \fn{A-Z} is being encoded to numbers using the following mapping:
\begin{Code}
'A' -> 1
'B' -> 2
...
'Z' -> 26
\end{Code}

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message \fn{"12"}, it could be decoded as \fn{"AB"} (1 2) or \fn{"L"} (12).

The number of ways decoding \fn{"12"} is 2.


\subsubsection{分析}
跟 Climbing Stairs (见 \S \ref{sec:climbing-stairs})很类似，不过多加一些判断逻辑。


\subsubsection{代码}
\begin{Code}
// LeetCode, Decode Ways
// 动规，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int numDecodings(const string &s) {
        if (s.empty() || s[0] == '0') return 0;

        int prev = 0;
        int cur = 1;
        // 长度为n的字符串，有 n+1个阶梯
        for (size_t i = 1; i <= s.size(); ++i) {
            if (s[i-1] == '0') cur = 0;

            if (i < 2 || !(s[i - 2] == '1' ||
                     (s[i - 2] == '2' && s[i - 1] <= '6')))
                prev = 0;

            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Climbing Stairs, 见 \S \ref{sec:climbing-stairs}
\myenddot


\section{Distinct Subsequences} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:distinct-subsequences}


\subsubsection{描述}
Given a string $S$ and a string $T$, count the number of distinct subsequences of $T$ in $S$.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, \fn{"ACE"} is a subsequence of \fn{"ABCDE"} while \fn{"AEC"} is not).

Here is an example:
$S$ = \fn{"rabbbit"}, $T$ = \fn{"rabbit"}

Return 3.


\subsubsection{分析}
设状态为$f(i,j)$，表示\fn{T[0,j]}在\fn{S[0,i]}里出现的次数。首先，无论\fn{S[i]}和\fn{T[j]}是否相等，若不使用\fn{S[i]}，则$f(i,j)=f(i-1,j)$；若\fn{S[i]==T[j]}，则可以使用\fn{S[i]}，此时$f(i,j)=f(i-1,j)+f(i-1, j-1)$。


\subsubsection{代码}
\begin{Code}
// LeetCode, Distinct Subsequences
// 二维动规+滚动数组
// 时间复杂度O(m*n)，空间复杂度O(n)
class Solution {
public:
    int numDistinct(const string &S, const string &T) {
        vector<int> f(T.size() + 1);
        f[0] = 1;
        for (int i = 0; i < S.size(); ++i) {
            for (int j = T.size() - 1; j >= 0; --j) {
                f[j + 1] += S[i] == T[j] ? f[j] : 0;
            }
        }

        return f[T.size()];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Word Break} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:word-break}


\subsubsection{描述}
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given \\
s = \fn{"leetcode"},\\
dict = \fn{["leet", "code"]}.

Return true because \fn{"leetcode"} can be segmented as \fn{"leet code"}.


\subsubsection{分析}
设状态为$f(i)$，表示\fn{s[0,i]}是否可以分词，则状态转移方程为
$$
f(i) = any\_of(f(j) \&\& s[j+1,i] \in dict),  0 \leq j < i
$$


\subsubsection{深搜}
\begin{Code}
// LeetCode, Word Break
// 深搜，超时
// 时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        return dfs(s, dict, 0, 0);
    }
private:
    static bool dfs(const string &s, unordered_set<string> &dict,
            size_t start, size_t cur) {
        if (cur == s.size()) {
            return dict.find(s.substr(start, cur-start+1)) != dict.end();
        }
        if (dfs(s, dict, start, cur+1)) return true;
        if (dict.find(s.substr(start, cur-start+1)) != dict.end())
            if (dfs(s, dict, cur+1, cur+1)) return true;
        return false;
    }
};
\end{Code}


\subsubsection{动规}
\begin{Code}
// LeetCode, Word Break
// 动规，时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        // 长度为n的字符串有n+1个隔板
        vector<bool> f(s.size() + 1, false);
        f[0] = true; // 空字符串
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.size()];
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Word Break II, 见 \S \ref{sec:word-break-ii}
\myenddot


\section{Word Break II} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:word-break-ii}


\subsubsection{描述}
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given  \\
s = \fn{"catsanddog"}, \\
dict = \fn{["cat", "cats", "and", "sand", "dog"]}.

A solution is \fn{["cats and dog", "cat sand dog"]}.


\subsubsection{分析}
在上一题的基础上，要返回解本身。


\subsubsection{代码}
\begin{Code}
// LeetCode, Word Break II
// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // 长度为n的字符串有n+1个隔板
        vector<bool> f(s.length() + 1, false);
        // prev[i][j]为true，表示s[j, i)是一个合法单词，可以从j处切开
        // 第一行未用
        vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length()));
        f[0] = true;
        for (size_t i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    f[i] = true;
                    prev[i][j] = true;
                }
            }
        }
        vector<string> result;
        vector<string> path;
        gen_path(s, prev, s.length(), path, result);
        return result;

    }
private:
    // DFS遍历树，生成路径
    void gen_path(const string &s, const vector<vector<bool> > &prev,
            int cur, vector<string> &path, vector<string> &result) {
        if (cur == 0) {
            string tmp;
            for (auto iter = path.crbegin(); iter != path.crend(); ++iter)
                tmp += *iter + " ";
            tmp.erase(tmp.end() - 1);
            result.push_back(tmp);
        }
        for (size_t i = 0; i < s.size(); ++i) {
            if (prev[cur][i]) {
                path.push_back(s.substr(i, cur - i));
                gen_path(s, prev, i, path, result);
                path.pop_back();
            }
        }
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Word Break, 见 \S \ref{sec:word-break}
\myenddot