判斷矩陣是否是一個 X 矩陣

【遍歷】主對角線上的下標(biāo)需滿足：i = j。反對角線上的下標(biāo)需滿足：i + j = n - 1。

統(tǒng)計放置房子的方式數(shù)

【線性 DP】兩側(cè)放置方案數(shù)獨立。定義f[i]表示前i個地塊的放置方案數(shù)，其中第i個地塊可放可不放，如果不放，那么i-1也放可不放，f[i] = f[i - 1]；若放，那么i-1不能放，i - 2可放可不放，綜上，f [i] = f[i - 1] + f[i - 2]。

拼接數(shù)組的最大分?jǐn)?shù)

【DP】設(shè)交換[l,r]范圍內(nèi)的元素，Σnums1' = Σnums1 - (nums1[l] + .. + num1[r]) + (nums2[l] + .. + nums[r])，合并相同下標(biāo)，等號右側(cè)變形為Σnums1 + (nums2[l] - nums1[l]) + .. + (nums2[r] - nums1[r])，設(shè)diff[i] = nums2[i] - nums1[i]，上式變?yōu)閟um(nums1) + diff[l] + ... + diff[r]。至此，轉(zhuǎn)換為最大子數(shù)組和問題，即求diff數(shù)組的最大子數(shù)組和，最后nums1,nums2各求一遍取max.

從樹中刪除邊的最小分?jǐn)?shù)

【DFS 時間戳】DFS 一棵樹的過程中，維護(hù)一個全局的時間戳 clock，每訪問一個新的節(jié)點，就將clock 加一（用時間戳代替直接判斷父子節(jié)點的好處是：不用記錄父子關(guān)系和祖父關(guān)系，省內(nèi)存）。同時，記錄進(jìn)入節(jié)點 x時的時間戳in[x]，和離開（遞歸結(jié)束）這個節(jié)點時的時間戳out[x]。由于 n 比較小，用 O(n^2)的時間枚舉兩條邊x1-y1，x2-y2，共有三種情況：①刪除的兩條邊在同一顆子樹內(nèi)，且 y1 是 x2 的祖先節(jié)點（或重合）;②刪除的兩條邊在同一顆子樹內(nèi)，且 y2 是 x1 的祖先節(jié)點（或重合）;③刪除的兩條邊分別屬于兩顆不相交的子樹。