題目簡述3989. 網(wǎng)格中保持一致的最大列數(shù)給定 m x n 網(wǎng)格 grid 和整數(shù) limit刪除若干列后至少保留一列若每一行中任意相鄰保留列的絕對值差都不超過 limit則稱該網(wǎng)格為一致的。求能保留的最大列數(shù)。約束m, n ≤ 250允許 O(n2·m) 的動(dòng)態(tài)規(guī)劃。---核心思路最長兼容子序列LIS 變種· 兼容性第 i 列與第 j 列i j可相鄰保留當(dāng)且僅當(dāng)所有行上 |grid[row][j] - grid[row][i]| ≤ limit。· DP 定義dp[j] 表示以第 j 列結(jié)尾的最長保留列數(shù)?！?轉(zhuǎn)移dp[j] max(dp[j], dp[i] 1)其中 i j 且 i 與 j 兼容。· 答案max(dp)。---Python3 實(shí)現(xiàn)pythonfrom typing import Listclass Solution:def maxConsistentColumns(self, grid: List[List[int]], limit: int) - int:m len(grid)n len(grid[0])# dp[j] 以第 j 列結(jié)尾的最長保留列數(shù)dp [1] * nans 1for j in range(n):for i in range(j):# 檢查列 i 和列 j 是否兼容compatible Truefor row in range(m):if abs(grid[row][j] - grid[row][i]) limit:compatible Falsebreakif compatible:dp[j] max(dp[j], dp[i] 1)ans max(ans, dp[j])return ans---復(fù)雜度分析指標(biāo) 復(fù)雜度時(shí)間復(fù)雜度 O(n2·m)最壞約 2502 × 250 1562.5 萬次比較Python 可輕松通過空間復(fù)雜度 O(n)僅一維 DP 數(shù)組---示例驗(yàn)證示例 1grid [[-2,0,3]], limit 2· 列 0 與 1 兼容差 2列 1 與 2 不兼容差 3列 0 與 2 不兼容差 5· 最優(yōu)保留 [0,1] → 答案 2示例 2grid [[1,-1,1],[2,2,2]], limit 1· 列 0 與 2 兼容兩行差均為 0· 最優(yōu)保留 [0,2] → 答案 2示例 3grid [[-5,5]], limit 9· 兩列差值 10 9不能同時(shí)保留只能保留一列 → 答案 1