題目簡(jiǎn)述3989. 網(wǎng)格中保持一致的最大列數(shù)給定 m x n 網(wǎng)格 grid 和整數(shù) limit刪除若干列后至少保留一列若每一行中任意相鄰保留列的絕對(duì)值差都不超過(guò) limit則稱該網(wǎng)格為一致的。求能保留的最大列數(shù)。約束m, n ≤ 250允許 O(n2·m) 的動(dòng)態(tài)規(guī)劃。---核心思路最長(zhǎng)兼容子序列LIS 變種· 兼容性第 i 列與第 j 列i j可相鄰保留當(dāng)且僅當(dāng)所有行上 |grid[row][j] - grid[row][i]| ≤ limit?！?DP 定義dp[j] 表示以第 j 列結(jié)尾的最長(zhǎng)保留列數(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é)尾的最長(zhǎng)保留列數(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 萬(wàn)次比較Python 可輕松通過(guò)空間復(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