1. 题目列表

• 除数博弈(一维简单动态规划）
• 节点与其祖先之间的最大差值（DFS，求最大差值）
• 最长等差数列（二维动态规划，理解状态转移）
• 从先序遍历还原二叉树（DFS建树，待学习）

2. 除数博弈

当前输赢状态i由前面i-1个状态所决定。
状态转移方程：
dp[i] = true, if i % j == 0 && dp[i - j] == fasle, j = 1, 2, ..., i - 1
dp[i] = false, else

代码：

class Solution {
public:
    bool divisorGame(int N) {
        bool win[N + 10];
        win[1] = false, win[2] = true;
        for (int i = 3; i <= N; i++){
            int j;
            for (j = 1; j < i; j++){
                if (i % j == 0 && !win[i - j]){
                    win[i] = true;
                    break;
                }
            }
            if (j == i)
                win[i] = false;
        }
        return win[N];
    }
};

3. 节点与其祖先之间的最大差值

求二叉树连通边上的最大差值。最佳方案是维护DFS中的最大值和最小值，到达边界时计算一次最大差值。（我的方法比较烦了...记录DFS路径，计算路径上的差值，其实一个道理。）

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> path, vals;
    int MAX = 0;
    int maxAncestorDiff(TreeNode* root) {
        path.clear();
        MAX = 0;
        path.push_back(root -> val);
        DFS(root);
        return MAX;
    }
    
    void DFS(TreeNode* root){
        if (root -> left == NULL && root -> right == NULL){
            vals = path; // 注意不能sort(path)，path在DFS不能被sort
            sort(vals.begin(), vals.end());
            int sub = vals[vals.size() - 1] - vals[0];
            if (sub > MAX){
                MAX = sub;
            }
            return ;
        }
        
        if (root -> left){
            path.push_back(root -> left -> val);
            DFS(root -> left);
            path.pop_back();
        }
        if (root -> right){
            path.push_back(root -> right -> val);
            DFS(root -> right);
            path.pop_back();
        }
    }
};

4. 最长等差数列

二维dp题：（关键理解状态转移的过程）

定义dp[i][j]表示以i为结尾的公差为j的最大等差序列长度。
则状态转移方程：
dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]], dp[j][A[i] - A[j]] + 1), j=0,1,2,...,i-1
根据等差数列的性质，以A[i]结尾的公差为A[i] - A[j]的状态依赖于以A[j]结尾公差也为A[i] - A[j]的状态。

初始dp数组所有可能的公差长度为1。

注意: 此处的公差可能为负值，因此可以偏移数组的第二维，或者使用vector<map>结构表示二维数组

代码：

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        vector< map<int, int> > dp(A.size());
        for (int i = 0; i < A.size(); i++){
            for (int j = i + 1; j < A.size(); j++){
                dp[i][A[j] - A[i]] = 1; // 公差计算：后面减前面的
            }
        }
        int MAX = 1;
        for (int i = 1; i < A.size(); i++){
            for (int j = 0; j < i; j++){
                // 注意：公差的计算是后面的减前面的，因此是A[i]-A[j]
                dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]], dp[j][A[i] - A[j]] + 1);
                MAX = max(dp[i][A[i] - A[j]], MAX);
            }
        }
        return MAX;
    }
};

5. 从先序遍历还原二叉树（复习二叉树的重构）

复杂的二叉树DFS重构。该题是给定二叉树的先序序列 + 节点的深度，并且规定了左节点优先，因此保证了重构二叉树的唯一性。

此外，也要复习二叉树的先序 + 中序、后序 + 中序重构。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pos = 0; //记录当前遍历到的位置，总指针
    string T;
    inline int read_val(int p) {
        int x = 0;
        for (; p < T.length() && isdigit(T[p]); ++ p)
            x = (x * 10) + (T[p] - '0');
        return x;
    }
    TreeNode* Dfs(int dep) {
        int cur = 0; //记录 '-' 的个数，表示下一个节点的深度
        for (int j = pos; j < T.length() && T[j] == '-'; ++ j) ++ cur;
        if (cur != dep) return NULL;
        pos += cur;
        TreeNode *u = new TreeNode(read_val(pos));
        while (pos < T.length() - 1 && isdigit(T[pos])) ++ pos; //跳过第一个数字后面的数字，在函数里已经计算过了
        u -> left = Dfs(dep + 1);
        u -> right = Dfs(dep + 1);
        return u;
    }
    TreeNode* recoverFromPreorder(string S) {
        T = S; return Dfs(0);
    }
    
};