动态规划定义

初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？

动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

动态规划实战：如何实现搜索引擎中的拼写纠错功能？

递归代码模板

分治代码模板

动态规划定义

MIT 动态规划课程最短路径算法

LeetCode题目：

1.最长公共子序列

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]
    }
}

2.三角形最小路径和

-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)"]!
        }
}

3.不同路径

-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
    }
}

4.不同路径 II

-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]
    }
}

5.不同路径 III

6.最长递增子序列

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
    }
}

7.打家劫舍

-升维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
    }
}

8.打家劫舍 II

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!)
    }
}

9.零钱兑换

-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()
        }
    }

10.零钱兑换 II

-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()
        }
    }
}

11.买卖股票的最佳时机

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]
    }
}

12.买卖股票的最佳时机 II

-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
    }
}

13.买卖股票的最佳时机 III

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]
    }
}

14.最佳买卖股票时机含冷冻期

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]
    }
}

15.买卖股票的最佳时机 IV

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]
       }
}

16.买卖股票的最佳时机含手续费

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]
        }
}

17.完全平方数

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!
    }
}

18.编辑距离（重点）

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]
    }
}

19.跳跃游戏

-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
    }
}

20.跳跃游戏 II

-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
        }
}

21.乘积最大子数组

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
    }
}

22.最小路径和

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]
    }
}

23.最大子序和

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)
    }
}

24.最大正方形

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
    }
}

25.青蛙过河

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
        }
    }
}

26.解码方法

27.任务调度器

28.最长有效括号

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
    }
}

29.矩形区域不超过 K 的最大数值和

30.分割数组的最大值

31.学生出勤记录 II

32.戳气球

33.使用最小花费爬楼梯

34.最大矩形

35. 不同的子序列

36.赛车