判断矩阵是否是一个 X 矩阵

【遍历】主对角线上的下标需满足：i = j。反对角线上的下标需满足：i + j = n - 1。

统计放置房子的方式数

【线性 DP】两侧放置方案数独立。定义f[i]表示前i个地块的放置方案数，其中第i个地块可放可不放，如果不放，那么i-1也放可不放，f[i] = f[i - 1]；若放，那么i-1不能放，i - 2可放可不放，综上，f [i] = f[i - 1] + f[i - 2]。

拼接数组的最大分数

【DP】设交换[l,r]范围内的元素，Σnums1' = Σnums1 - (nums1[l] + .. + num1[r]) + (nums2[l] + .. + nums[r])，合并相同下标，等号右侧变形为Σnums1 + (nums2[l] - nums1[l]) + .. + (nums2[r] - nums1[r])，设diff[i] = nums2[i] - nums1[i]，上式变为sum(nums1) + diff[l] + ... + diff[r]。至此，转换为最大子数组和问题，即求diff数组的最大子数组和，最后nums1,nums2各求一遍取max.

从树中删除边的最小分数

【DFS 时间戳】DFS 一棵树的过程中，维护一个全局的时间戳 clock，每访问一个新的节点，就将clock 加一（用时间戳代替直接判断父子节点的好处是：不用记录父子关系和祖父关系，省内存）。同时，记录进入节点 x时的时间戳in[x]，和离开（递归结束）这个节点时的时间戳out[x]。由于 n 比较小，用 O(n^2)的时间枚举两条边x1-y1，x2-y2，共有三种情况：①删除的两条边在同一颗子树内，且 y1 是 x2 的祖先节点（或重合）;②删除的两条边在同一颗子树内，且 y2 是 x1 的祖先节点（或重合）;③删除的两条边分别属于两颗不相交的子树。