本文涉及知識點

C++動態規劃

3276. 選擇矩陣中單元格的最大得分

給你一個由正整數構成的二維矩陣 grid。
你需要從矩陣中選擇 一個或多個 單元格，選中的單元格應滿足以下條件：
所選單元格中的任意兩個單元格都不會處于矩陣的 同一行。
所選單元格的值 互不相同。
你的得分為所選單元格值的總和。
返回你能獲得的 最大 得分。
示例 1：
輸入： grid = [[1,2,3],[4,3,2],[1,1,1]]
輸出： 8
解釋：
選擇上圖中用彩色標記的單元格，對應的值分別為 1、3 和 4 。
示例 2：
輸入： grid = [[8,7,6],[8,3,2]]
輸出： 15
解釋：
選擇上圖中用彩色標記的單元格，對應的值分別為 7 和 8 。
提示：
1 <= grid.length, grid[i].length <= 10
1 <= grid[i][j] <= 100

狀態壓縮動態規劃

各行升序排序。R是網格的行數，M是$max(grid[r][c])$

動態規劃的狀態表示

我們選中的降序選擇。
dp[m][min] ,(1<<r)&m 表示第r行是否選擇。iMin表示選擇的最小值。$iMin\in [0,101]$。
空間復雜度：$O(2^{N}M)$

動態規劃的填表順序

m從0到大，iMin任意升序。枚舉前驅狀態。

動態規劃的轉移方程

每種狀態： 枚舉從第r行選擇：
it = lower(grid[r],iMin)
如果it 是首元素：
MaxSelf(dp[m ^(1<<r)][min],dp[m][min])
不是首元素：
–it。
MaxSelf(dp[m ^(1<<r)][min] ,dp[m][min]+*it)
時間復雜度：$O(N{2}^{N}MlogC)$

動態規劃的初始值

全為0

動態規劃的返回值

dp.back().back()