LeetCode题目：
class Solution {
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
let text1Arr = Array(text1), text2Arr = Array(text2)
let m = text1.count, n = text2.count
// 构造二维数组 全0
var arr = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
for i in 1..<arr.count {
for j in 1..<arr.first!.count {
if text1Arr[j - 1] == text2Arr[i - 1] {
arr[i][j] = 1 + arr[i - 1][j - 1]
} else {
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
}
}
}
return arr[n][m]
}
}
-Bottom-Up 技巧是从倒数第二层开始递推
class Solution {
func minimumTotal(_ triangle: [[Int]]) -> Int {
var dp = triangle
for i in (0..<dp.count - 1).reversed() {
for j in 0..<dp[i].count {
dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1])
}
}
return dp[0][0]
}
}
-Up-Bottom 递归加记忆化搜索
class Solution {
var memDict = Dictionary<String, Int>()
func minimumTotal(_ triangle: [[Int]]) -> Int {
return helper(i: 0, j: 0, triangle: triangle)
}
func helper(i: Int, j: Int, triangle: [[Int]]) -> Int{
if i == triangle.count - 1 {
return triangle[i][j]
}
guard memDict["\(i) * \(j)"] != nil else {
let left = helper(i: i + 1, j: j, triangle: triangle)
let right = helper(i: i + 1, j: j + 1, triangle: triangle)
memDict["\(i) * \(j)"] = min(left, right) + triangle[i][j]
return memDict["\(i) * \(j)"]!
}
return memDict["\(i) * \(j)"]!
}
}
-Bottom-Up DP方程递推出最终结果
class Solution {
func uniquePaths(_ m: Int, _ n: Int) -> Int {
if m == 1 || n == 1 {
return 1
}
var arr = Array(repeating: Array(repeating: 0, count: n), count: m)
for i in 0..<n {
arr[m - 1][i] = 1
}
for j in 0..<m {
arr[j][n - 1] = 1
}
var i = m - 2, j = n - 2
repeat {
arr[i][j] = arr[i + 1][j] + arr[i][j + 1]
if i == 0 && j == 0 {
break
}
if i != 0 {
i -= 1
} else {
i = m - 2
j -= 1
}
} while true
return arr[0][0]
}
}
-Up-Bottom* 递归 + 记忆化搜索
class Solution {
var memDict: Dictionary<String, Int> = Dictionary<String, Int>()
func uniquePaths(_ m: Int, _ n: Int) -> Int {
return countPath(m: m, n: n, row: 0, col: 0)
}
func countPath(m: Int, n: Int, row: Int, col: Int) -> Int {
if !validSqure(m: m, n: n, row: row, col: col) { return 0 }
if isAtEnd(m: m, n: n, row: row, col: col) { return 1 }
//memoize
guard memDict["\(row) * \(col)"] != nil else {
memDict["\(row) * \(col)"] = countPath(m: m, n: n, row: row + 1, col: col) + countPath(m: m, n: n, row: row, col: col + 1)
return memDict["\(row) * \(col)"]!
}
return memDict["\(row) * \(col)"]!
}
func validSqure(m: Int, n: Int, row: Int, col: Int) -> Bool {
if row > m - 1 { return false }
if col > n - 1 { return false }
return true
}
func isAtEnd(m: Int, n: Int, row: Int, col: Int) -> Bool {
if row == m - 1 { return true }
if col == n - 1 { return true }
return false
}
}
-Up-Bottom* 递归并处理特殊情况
class Solution {
var memDict: Dictionary<String, Int> = Dictionary<String, Int>()
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
guard obstacleGrid[obstacleGrid.count - 1][obstacleGrid.first!.count - 1] != 1 else { return 0 }
// 横条
if obstacleGrid.count == 1 {
if obstacleGrid.first!.contains(1) {
return 0
} else {
return 1
}
}
// 竖条
if obstacleGrid.first!.count == 1 {
for arr in obstacleGrid {
if arr.first == 1 {
return 0
}
}
return 1
}
return countPath(grid: obstacleGrid, i: 0, j: 0)
}
func countPath(grid: [[Int]], i: Int, j: Int) -> Int {
if !validCourt(grid: grid, i: i, j: j) { return 0 }
if grid[i][j] == 1 { return 0}
if isAtEnd(grid: grid, i: i, j: j) {
if hasBarrierBehind(grid: grid, i: i, j: j) {
return 0
} else {
return 1
}
}
guard memDict["\(i) * \(j)"] != nil else {
memDict["\(i) * \(j)"] = countPath(grid: grid, i: i, j: j + 1) + countPath(grid: grid, i: i + 1, j: j)
return memDict["\(i) * \(j)"]!
}
return memDict["\(i) * \(j)"]!
}
func validCourt(grid: [[Int]], i: Int, j: Int) -> Bool {
if (i > grid.count - 1) || (j > grid.first!.count - 1) {
return false
}
return true
}
func isAtEnd(grid: [[Int]], i: Int, j: Int) -> Bool {
if (i == grid.count - 1) || (j == grid.first!.count - 1) {
return true
}
return false
}
func hasBarrierBehind(grid: [[Int]], i: Int, j: Int) -> Bool {
if j == grid.first!.count - 1 {
//右边竖条
for k in i...grid.count - 1 {
if grid[k][grid.first!.count - 1] == 1 {
return true
}
}
} else {
//底下横条
for k in j...grid.first!.count - 1 {
if grid[grid.count - 1][k] == 1 {
return true
}
}
}
return false
}
}
-Bottom-Up DP*方程递推出结果先给两边处理了然后正常递推
class Solution {
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
guard obstacleGrid[obstacleGrid.count - 1][obstacleGrid.first!.count - 1] != 1 else {
return 0
}
// 横条
if obstacleGrid.count == 1 {
if obstacleGrid.first!.contains(1) {
return 0
} else {
return 1
}
}
// 竖条
if obstacleGrid.first!.count == 1 {
for arr in obstacleGrid {
if arr.first == 1 {
return 0
}
}
return 1
}
var arr = obstacleGrid
let m = arr.count, n = arr.first!.count
for i in 0..<n - 1 {
if arr[m - 1][i] == 1 {
// 前边都得置0
for j in 0...i {
arr[m - 1][j] = 0
}
} else {
arr[m - 1][i] ^= 1
}
}
for j in 0..<m - 1 {
if arr[j][n - 1] == 1 {
// 前边都得置0
for i in 0...j {
arr[i][n-1] = 0
}
} else {
arr[j][n - 1] ^= 1
}
}
var i = m - 2, j = n - 2
repeat{
if arr[i][j] == 1 {
arr[i][j] = 0
} else {
arr[i][j] = arr[i][j + 1] + arr[i + 1][j]
}
if i == 0 && j == 0 {
break
}
if i != 0 {
i -= 1
} else {
i = m - 2
j -= 1
}
} while true
return arr[0][0]
}
}
class Solution {
func lengthOfLIS(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return 1
}
var dpArr = Array(repeating: 1, count: nums.count)
var res = 0
for i in 1..<dpArr.count {
for j in 0..<i {
if nums[i] > nums[j] {
dpArr[i] = max(dpArr[i], dpArr[j] + 1)
}
}
res = max(dpArr[i], res)
}
return res
}
}
-升维DP
class Solution {
func rob(_ nums: [Int]) -> Int {
guard nums.count > 0 else {
return 0
}
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: nums.count)
dpArr[0][0] = 0
dpArr[0][1] = nums[0]
for i in 1..<nums.count {
dpArr[i][0] = max(dpArr[i - 1][0], dpArr[i - 1][1])
dpArr[i][1] = nums[i] + dpArr[i - 1][0]
}
return max(dpArr[nums.count - 1][0], dpArr[nums.count - 1][1])
}
}
-不升维DP
class Solution {
func rob(_ nums: [Int]) -> Int {
guard nums.count > 0 else {
return 0
}
if nums.count == 1 {
return nums[0]
}
var dpArr = Array(repeating: 0, count: nums.count)
dpArr[0] = nums[0]
dpArr[1] = max(nums[0], nums[1])
for i in 2..<nums.count {
dpArr[i] = max(dpArr[i - 1], dpArr[i - 2] + nums[i])
}
return dpArr[nums.count - 1]
}
}
-优化掉不升维DP中的数组
class Solution {
func rob(_ nums: [Int]) -> Int {
var pre = 0
var now = 0
for i in nums {
let temp = max(pre + i, now)
pre = now
now = temp
}
return now
}
}
class Solution {
//首尾相连，就他它转化成两个分别来求，最后取大的
func rob(_ nums: [Int]) -> Int {
var nums = nums
guard nums.count > 0 else {
return 0
}
if nums.count == 1 {
return nums[0]
}
if nums.count == 2 {
return max(nums.first!, nums.last!)
}
let tempLast = nums.removeLast()
let dpArrContainFirst = nums
nums = nums + [tempLast]
let tempFirst = nums.removeFirst()
let dpArrContainLast = nums
nums = [tempFirst] + nums
var dpArr1 = Array(repeating: 0, count: dpArrContainFirst.count)
dpArr1[0] = dpArrContainFirst[0]
dpArr1[1] = max(dpArrContainFirst[0], dpArrContainFirst[1])
for i in 2..<dpArrContainFirst.count {
dpArr1[i] = max(dpArr1[i - 1], dpArr1[i - 2] + dpArrContainFirst[i])
}
var dpArr2 = Array(repeating: 0, count: dpArrContainLast.count)
dpArr2[0] = dpArrContainLast[0]
dpArr2[1] = max(dpArrContainLast[0], dpArrContainLast[1])
for i in 2..<dpArrContainLast.count {
dpArr2[i] = max(dpArr2[i - 1], dpArr2[i - 2] + dpArrContainLast[i])
}
return max(dpArr1.last!, dpArr2.last!)
}
}
-DP
class Solution {
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
guard amount > 0 else {
return 0
}
var dpArr = Array(repeating: amount + 1, count: amount + 1)
dpArr[0] = 0
for i in 1...amount {
for j in 0..<coins.count {
if coins[j] <= i {
dpArr[i] = min(dpArr[i], dpArr[i - coins[j]] + 1)
}
}
}
return dpArr[amount] > amount ? -1 : dpArr[amount]
}
}
-超出时间限制的DFS + 回溯
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
var res = Array<Int>()
var curCoinArray = Array<Int>()
dfs(coins: coins.sorted(by: >), amount: amount, cur: 0, res: &res, curCoinArray: &curCoinArray)
return res.count == 0 ? -1 : res.first!
}
func dfs(coins: [Int], amount: Int, cur: Int, res: inout Array<Int>, curCoinArray: inout [Int]) {
if cur == amount {
if res.count != 0 {
if res.first! >= curCoinArray.count {
res.removeFirst()
res.append(curCoinArray.count)
}
} else {
res.append(curCoinArray.count)
}
return
}
if cur > amount { return }
for (index, i) in coins.enumerated() {
curCoinArray.append(coins[index])
dfs(coins: coins, amount: amount, cur: cur + i, res: &res, curCoinArray: &curCoinArray)
curCoinArray.removeLast()
}
}
-DP
class Solution {
func change(_ amount: Int, _ coins: [Int]) -> Int {
if amount == 0 {
return 1
}
var dpArr = Array(repeating: 0, count: amount + 1)
dpArr[0] = 1
for coin in coins {
if coin > amount { continue }
for x in coin...amount {
dpArr[x] += dpArr[x - coin]
}
}
return dpArr.last!
}
}
-超时的DFS 不好再继续优化(剪枝条件不好找)
class Solution {
func change(_ amount: Int, _ coins: [Int]) -> Int {
var res = Set<Array<Int>>()
var cur = Array<Int>()
dfs(amount: amount, coints: coins, res: &res, cur: &cur)
return res.count
}
func dfs(amount: Int, coints: [Int], res: inout Set<Array<Int>>, cur: inout [Int]) {
if amount == 0 {
res.insert(cur.sorted())
return
}
if amount < 0 {
return
}
for i in coints {
cur.append(i)
dfs(amount: amount - i, coints: coints, res: &res, cur: &cur)
cur.removeLast()
}
}
}
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
let prices = [0] + prices
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
dpArr[0][0] = 0
dpArr[0][1] = Int(-1000000000)
for i in 1...prices.count - 1 {
for j in 0...1 {
if j == 0 {
dpArr[i][j] = max(dpArr[i - 1][1] + prices[i], dpArr[i - 1][0])
} else {
// j == 1
dpArr[i][j] = max(-prices[i], dpArr[i - 1][1])
}
}
}
return dpArr[prices.count - 1][0]
}
}
-DP
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
let prices = [0] + prices
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
dpArr[0][0] = 0
dpArr[0][1] = Int(-1000000)
for i in 1...prices.count - 1 {
for j in 0...1 {
if j == 0 {
dpArr[i][j] = max(dpArr[i - 1][1] + prices[i], dpArr[i - 1][0])
} else {
dpArr[i][j] = max(dpArr[i - 1][0] - prices[i], dpArr[i - 1][1])
}
}
}
return dpArr[prices.count - 1][0]
}
}
贪心
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var everyProfit = 0
var res = 0
for (index, i) in prices.enumerated() {
if index == prices.count - 1 {
break
}
everyProfit = prices[index + 1] - i
if everyProfit > 0 {
res += everyProfit
}
}
return res
}
}
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
let usePrices = [0] + prices
var dpArr = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: 3), count: usePrices.count)
dpArr[0][0][0] = 0
dpArr[0][0][1] = -1000000
dpArr[0][1][0] = 0
dpArr[0][1][1] = -1000000
dpArr[0][2][0] = 0
dpArr[0][2][1] = -1000000
for i in 1..<usePrices.count {
for k in 1...2 {
for o in 0...1 {
if o == 0 {
dpArr[i][k][0] = max(dpArr[i - 1][k][0], dpArr[i - 1][k][1] + usePrices[i])
} else {
dpArr[i][k][1] = max(dpArr[i - 1][k][1], dpArr[i - 1][k - 1][0] - usePrices[i])
}
}
}
}
return dpArr[usePrices.count - 1][2][0]
}
}
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
let prices = [0] + prices
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
dpArr[0][0] = 0
dpArr[0][1] = -10000000
for i in 1...prices.count - 1 {
for j in 0...1 {
if j == 0 {
dpArr[i][j] = max(dpArr[i - 1][1] + prices[i], dpArr[i - 1][0])
} else {
// j == 1
dpArr[i][j] = max(dpArr[i - 1][0] - prices[i], dpArr[i - 1][1])
}
}
}
return dpArr[prices.count - 1][0]
}
}
class Solution {
func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
guard k > 0 else {
return 0
}
let usePrices = [0] + prices
var dpArr = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: k + 1), count: usePrices.count)
for i in 0...k {
for j in 0...1 {
if j == 0 {
dpArr[0][i][j] = 0
} else {
dpArr[0][i][j] = -1000000
}
}
}
for i in 1..<usePrices.count {
for j in 1...k {
for o in 0...1 {
if o == 0 {
dpArr[i][j][0] = max(dpArr[i - 1][j][0], dpArr[i - 1][j][1] + usePrices[i])
} else {
dpArr[i][j][1] = max(dpArr[i - 1][j][1], dpArr[i - 1][j - 1][0] - usePrices[i])
}
}
}
}
return dpArr[usePrices.count - 1][k][0]
}
}
class Solution {
func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
let prices = [0] + prices
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
dpArr[0][0] = 0
dpArr[0][1] = Int(-1000000)
for i in 1...prices.count - 1 {
for j in 0...1 {
if j == 0 {
dpArr[i][j] = max(dpArr[i - 1][1] + prices[i], dpArr[i - 1][0])
} else {
dpArr[i][j] = max(dpArr[i - 1][0] - prices[i] - fee, dpArr[i - 1][1])
}
}
}
return dpArr[prices.count - 1][0]
}
}
class Solution {
func numSquares(_ n: Int) -> Int {
var dpArr = Array(repeating: 0, count: n + 1)
let sqrtN = Int(sqrt(Double(n)))
dpArr[0] = 0
for i in 1...n {
dpArr[i] = i
for j in 1...sqrtN {
if i - j * j >= 0 {
dpArr[i] = min(dpArr[i], dpArr[i - j * j] + 1)
}
}
}
return dpArr.last!
}
}
class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
if word1 == "" || word2 == "" {
return max(word1.count, word2.count)
}
let word1Arr = Array(word1)
let word2Arr = Array(word2)
var dpArr = Array(repeating: Array(repeating: 0, count: word2Arr.count + 1), count: word1Arr.count + 1)
// 哨兵初始化
for i in 0...word2Arr.count {
dpArr[0][i] = i
}
for i in 0...word1Arr.count {
dpArr[i][0] = i
}
for i in (1...word1Arr.count) {
for j in (1...word2Arr.count) {
if word1Arr[i - 1] == word2Arr[j - 1] {
dpArr[i][j] = dpArr[i - 1][j - 1]
} else {
dpArr[i][j] = min(dpArr[i][j - 1] + 1, dpArr[i - 1][j] + 1, dpArr[i - 1][j - 1] + 1)
}
}
}
return dpArr[word1.count][word2.count]
}
}
-DP
class Solution {
func canJump(_ nums: [Int]) -> Bool {
guard nums.count > 1 else {
return true
}
if nums.count == 2 {
return nums.first! >= 1 ? true : false
}
if nums.first! == 0 {
return false
}
var dpArr = nums
var res = 0
for i in 1..<nums.count - 1 {
dpArr[i] = max(dpArr[i - 1], i + nums[i])
if dpArr[i] == i {
return false
}
res = max(res, dpArr[i])
}
return (res >= nums.count - 1) ? true : false
}
}
-贪心
class Solution {
func canJump(_ nums: [Int]) -> Bool {
if nums.count == 1 {
return true
}
var cover = 0
var i = 0
while cover < nums.count - 1 {
if i > cover {
return false
}
cover = max(i + nums[i], cover)
i += 1
}
return true
}
}
-DP
class Solution {
func jump(_ nums: [Int]) -> Int {
if nums.count == 1 {
return 0
}
if nums.count == 2 {
return 1
}
var dpArr = Array(repeating: 10000000, count: nums.count)
dpArr[0] = 0
var cover = nums.first!
for i in 1..<nums.count {
if cover > nums.count - 1 {
cover = nums.count - 1
}
for j in i...cover {
dpArr[j] = min(dpArr[i - 1] + 1, dpArr[j])
}
cover = max(cover, i + nums[i])
}
return dpArr.last!
}
}
贪心
class Solution {
var level = 0
func jump(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return 0
}
var cover = 0
var i = 0
while cover < nums.count - 1 {
cover = max(cover, i + nums[i])
i += 1
}
level += 1
jump(Array(nums[0...i - 1]))
return level
}
}
class Solution {
func maxProduct(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return nums.first!
}
var res = -100000000
var dpArr = Array(repeating: Array(repeating: 0, count: 2), count: nums.count + 1)
dpArr[0][0] = 1
dpArr[0][1] = 1
for i in 1...nums.count {
dpArr[i][0] = nums[i - 1]
dpArr[i][1] = nums[i - 1]
}
for i in 1..<dpArr.count {
for j in 0...1 {
if j == 0 {
// positive
dpArr[i][j] = max(dpArr[i - 1][0] * nums[i - 1], dpArr[i - 1][1] * nums[i - 1], nums[i - 1])
res = max(res, dpArr[i][j])
} else {
// negtive
dpArr[i][j] = min(dpArr[i - 1][0] * nums[i - 1], dpArr[i - 1][1] * nums[i - 1], nums[i - 1])
}
}
}
return res
}
}
class Solution {
func minPathSum(_ grid: [[Int]]) -> Int {
var dpArr = grid
for i in 1..<grid.count {
dpArr[i][0] = dpArr[i - 1][0] + dpArr[i][0]
}
for i in 1..<grid.first!.count {
dpArr[0][i] = dpArr[0][i - 1] + dpArr[0][i]
}
for i in 1..<dpArr.count {
for j in 1..<dpArr.first!.count {
dpArr[i][j] = min(dpArr[i - 1][j], dpArr[i][j - 1]) + dpArr[i][j]
}
}
return dpArr[dpArr.count - 1][dpArr.first!.count - 1]
}
}
class Solution {
func maxSubArray(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return nums.first!
}
var dpArr = [-1000000] + nums
var res = -1000000
for i in 1..<dpArr.count {
dpArr[i] = max(dpArr[i - 1] + dpArr[i], dpArr[i])
res = max(res, dpArr[i])
}
return Int(res)
}
}
class Solution {
func maximalSquare(_ matrix: [[Character]]) -> Int {
var dpArr = Array(repeating: Array(repeating: 0, count: matrix.first!.count + 1), count: matrix.count + 1)
var res = 0
for i in 1..<dpArr.count {
for j in 1..<dpArr.first!.count {
if matrix[i - 1][j - 1] == "1" {
dpArr[i][j] = min(dpArr[i - 1][j], dpArr[i - 1][j - 1], dpArr[i][j - 1]) + 1
res = max(res, dpArr[i][j])
}
}
}
return res * res
}
}
class Solution {
func canCross(_ stones: [Int]) -> Bool {
if stones.count == 2 {
if stones.last! > 1 {
return false
} else {
return true
}
}
var dict: Dictionary<Int, Set<Int>> = Dictionary<Int, Set<Int>>()
dict.updateValue([1], forKey: stones[1] + 1)
dict.updateValue([2], forKey: stones[1] + 2)
for i in stones[2...] {
guard let setValue = dict[i] else {
continue
}
for s in setValue {
if var set1 = dict[i + s - 1] {
set1.insert(s - 1)
dict[i + s - 1] = set1
} else {
dict.updateValue( [s - 1], forKey: i + s - 1)
}
if var set2 = dict[i + s] {
set2.insert(s)
dict[i + s] = set2
} else {
dict.updateValue([s], forKey: i + s)
}
if var set3 = dict[i + s + 1] {
set3.insert(s + 1)
dict[i + s + 1] = set3
} else {
dict.updateValue([s + 1], forKey: i + s + 1)
}
}
}
if dict.keys.contains(stones.last!) {
return true
} else {
return false
}
}
}
class Solution {
func longestValidParentheses(_ s: String) -> Int {
guard s.count >= 2 else {
return 0
}
let sArr = Array(s)
var dpArr = Array(repeating: 0, count: s.count)
var res = 0
for i in 1..<sArr.count {
if sArr[i] == "(" {
dpArr[i] = 0
} else {
// ")"
if sArr[i - 1] == "(" {
// 匹配上了 ".....()"
if i - 2 > 0 {
// sArr[i - 2]存在
dpArr[i] = 2 + dpArr[i - 2]
} else {
// sArr[i - 2]不存在
dpArr[i] = 2
}
} else {
// 没匹配上 ")" ".....))" 考察 sArr[i - dp[i - 1] -1]
if i - dpArr[i - 1] - 1 < 0 {
// sArr[i - dpArr[i - 1] -1] 不存在
dpArr[i] = 0
} else {
// sArr[i - dpArr[i - 1] -1] 存在
if sArr[i - dpArr[i - 1] - 1] == ")" {
// "...).....))"
dpArr[i] = 0
} else {
// "...(.....))" 考察 sArr[i - dpArr[i - 1] - 2]
if i - dpArr[i - 1] - 2 < 0 {
// sArr[i - dpArr[i - 1] - 2] 不存在
dpArr[i] = 2 + dpArr[i - 1]
} else {
// sArr[i - dp[i - 1] - 2] 存在
dpArr[i] = 2 + dpArr[i - 1] + dpArr[i - dpArr[i - 1] - 2]
}
}
}
}
}
res = max(res, dpArr[i])
}
return res
}
}
网友评论