> For the complete documentation index, see [llms.txt](https://zyj.gitbook.io/algorithm-pattern-swift/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zyj.gitbook.io/algorithm-pattern-swift/ji-chu-suan-fa-pian/dp.md).

# 动态规划

## 背景

先从一道题目开始\~

如题 [triangle](https://leetcode-cn.com/problems/triangle/)

> 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

```
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
```

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

使用 DFS（遍历 或者 分治法）

遍历

![image.png](https://img.fuiboom.com/img/dp_triangle.png)

分治法

![image.png](https://img.fuiboom.com/img/dp_dc.png)

优化 DFS，缓存已经被计算的值（称为：记忆化搜索 本质上：动态规划）

![image.png](https://img.fuiboom.com/img/dp_memory_search.png)

```swift
//https://leetcode-cn.com/problems/triangle/solution/swift-shen-du-you-xian-di-gui-huan-cun-yi-jing-bei/
//自顶向下的递归，深度优先搜索，缓存已经被计算的值
//执行用时：60 ms, 在所有 Swift 提交中击败了8.37%的用户
//内存消耗：21.4 MB, 在所有 Swift 提交中击败了5.00%的用户
func minimumTotal(_ triangle: [[Int]]) -> Int {
    var cache =  Dictionary<String, Int>()
    func dfs(_ i: Int, _ j: Int) -> Int {
        if i == triangle.count {
            return 0
        }
        if let item = cache["\(i)-\(j)"] {
            return item
        }
        let res = min(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j]
        cache["\(i)-\(j)"] = res
        return res
    }
    return dfs(0,0)
}
```

动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划

动态规划和 DFS 区别

* 二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 DFS，就可以解决
* 像 triangle 这种是有重复走的情况，**子问题是有交集**，所以可以用动态规划来解决

动态规划，自底向上

```swift
//https://leetcode-cn.com/problems/triangle/solution/swift-dong-tai-gui-hua-zi-di-xiang-shang-kong-jian/
//动态规划（自底向上），空间优化O(N)
//执行用时：44 ms, 在所有 Swift 提交中击败了91.16%的用户
//内存消耗：20.4 MB, 在所有 Swift 提交中击败了100.00%的用户
func minimumTotal(_ triangle: [[Int]]) -> Int {
    let count = triangle.count
    /*
    var dp = [[Int]](repeating: [Int](repeating: 0, count: count + 1), count: count + 1)
    for i in (0...(count-1)).reversed()  {
        for j in 0...i {
            dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
        }
    }
    return dp[0][0]
    */
    //空间优化O(N)
    var dp = [Int](repeating: 0, count: count + 1)
    for i in (0...(count-1)).reversed()  {
        for j in 0...i {
            dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
        }
    }
    return dp[0]
}
```

动态规划，自顶向下

```swift
//https://leetcode-cn.com/problems/triangle/solution/swift-dong-tai-gui-hua-zi-ding-xiang-xia-kong-jian/
//动态规划（自顶向下），空间优化O(N)
//执行用时：48 ms, 在所有 Swift 提交中击败了71.16%的用户
//内存消耗：20.9 MB, 在所有 Swift 提交中击败了85.00%的用户
func minimumTotal(_ triangle: [[Int]]) -> Int {
    let count = triangle.count
    /*
    var dp = [[Int]](repeating: [Int](repeating: 0, count: count), count: count)
    dp[0][0] = triangle[0][0]
    for i in 1..<count {
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        for j in 1..<i {
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
        }
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]
    }
    var minTotal = dp[count-1][0]
    for i in 1..<count {
        minTotal = min(minTotal,dp[count-1][i])
    }
    return minTotal
    */
    //空间优化O(N)
    var dp = [Int](repeating: 0, count: count)
    dp[0] = triangle[0][0]
    for i in 1..<count {
        dp[i] = dp[i-1] + triangle[i][i]
        for j in (1..<i).reversed() {
            dp[j] = min(dp[j],dp[j-1]) + triangle[i][j]
        }
        dp[0] = dp[0] + triangle[i][0]
    }
    var minTotal = dp[0]
    for i in 1..<count {
        minTotal = min(minTotal,dp[i])
    }
    return minTotal
}
```

## 递归和动规关系

递归是一种程序的实现方式：函数的自我调用

```swift
Function(x) {
    ...
    Funciton(x-1);
    ...
}
```

动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)

## 使用场景

满足两个条件

* 满足以下条件之一
  * 求最大/最小值（Maximum/Minimum ）
  * 求是否可行（Yes/No ）
  * 求可行个数（Count(\*) ）
* 满足不能排序或者交换（Can not sort / swap ）

如题：[longest-consecutive-sequence](https://leetcode-cn.com/problems/longest-consecutive-sequence/) 位置可以交换，所以不用动态规划

## 四点要素

1. **状态 State**
   * 灵感，创造力，存储小规模问题的结果
2. 方程 Function
   * 状态之间的联系，怎么通过小的状态，来算大的状态
3. 初始化 Intialization
   * 最极限的小状态是什么, 起点
4. 答案 Answer
   * 最大的那个状态是什么，终点

## 常见四种类型

1. Matrix DP (10%)
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)

> 注意点
>
> * 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法

## 1、矩阵类型（10%）

### [minimum-path-sum](https://leetcode-cn.com/problems/minimum-path-sum/)

> 给定一个包含非负整数的 *m* x *n* 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

思路：动态规划 1、state: f\[x]\[y]从起点走到 x,y 的最短路径 2、function: f\[x]\[y] = min(f\[x-1]\[y], f\[x]\[y-1]) + A\[x]\[y] 3、intialize: f\[0]\[0] = A\[0]\[0]、f\[i]\[0] = sum(0,0 -> i,0)、 f\[0]\[i] = sum(0,0 -> 0,i) 4、answer: f\[n-1]\[m-1]

```swift
//https://leetcode-cn.com/problems/minimum-path-sum/solution/swift-dong-tai-gui-hua-zi-di-xiang-shang-kong-ji-2/
//动态规划（自底向上），空间优化O(N)
//执行用时：76 ms, 在所有 Swift 提交中击败了83.78%的用户
//内存消耗：20.9 MB, 在所有 Swift 提交中击败了76.92%的用户
func minPathSum(_ grid: [[Int]]) -> Int {
    /*
     let m = grid.count
     guard m != 0 else{
     return 0
     }
     let n = grid[0].count
     var dp = [[Int]](repeating: [Int](repeating: Int.max, count: n + 1), count: m + 1)
     dp[m][n-1] =  0
     for i in (0..<m).reversed()  {
     for j in (0..<n).reversed()  {
     dp[i][j] = min(dp[i+1][j],dp[i][j+1]) + grid[i][j]
     }
     }
     return dp[0][0]
     */
    //空间优化O(N)
    let m = grid.count
    guard m != 0 else{
        return 0
    }
    let n = grid[0].count

    var dp =  grid[m-1]
    for i in (0..<(n-1)).reversed() {
        dp[i] += dp[i+1]
    }
    dp.append(Int.max)//dp长度是n+1

    for i in (0..<(m-1)).reversed()  {
        for j in (0..<n).reversed()  {
            dp[j] = min(dp[j],dp[j+1]) + grid[i][j]
        }
    }
    return dp[0]
}

//https://leetcode-cn.com/problems/minimum-path-sum/solution/swift-zi-ding-xiang-xia-de-di-gui-shen-du-you-xian/
//自顶向下的递归，深度优先搜索，缓存已经被计算的值
//执行用时：120 ms, 在所有 Swift 提交中击败了5.41%的用户
//内存消耗：22.5 MB, 在所有 Swift 提交中击败了5.77%的用户
func minPathSum_a(_ grid: [[Int]]) -> Int {
    let m = grid.count
    guard m != 0 else{
        return 0
    }
    let n = grid[0].count

    var cache =  Dictionary<String, Int>()
    func dfs(_ i: Int, _ j: Int) -> Int {
        if i == m || j == n {
            //m*n的最后一个特殊处理：它的右边或下边为0
            if (i == m - 1) {//(i == m - 1) || (j == n - 1)
                return 0
            }
            return Int.max
        }
        if let item = cache["\(i)-\(j)"] {
            return item
        }
        let res = min(dfs(i+1,j),dfs(i,j+1))+grid[i][j]
        cache["\(i)-\(j)"] = res
        return res
    }
    return dfs(0,0)
}
```

### [unique-paths](https://leetcode-cn.com/problems/unique-paths/)

> 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？

```swift
//https://leetcode-cn.com/problems/unique-paths/solution/swift-dong-tai-gui-hua-zi-di-xiang-shang-kong-ji-3/
//动态规划（自底向上），空间优化O(N)，注意下开始行列
//执行用时：8 ms, 在所有 Swift 提交中击败了63.64%的用户
//内存消耗：20.7 MB, 在所有 Swift 提交中击败了62.79%的用户
func uniquePaths(_ m: Int, _ n: Int) -> Int {
    /*
    var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
    dp[m][n-1] =  1 //主要是处理最底部一行和最右边的一列
    for i in (0..<m).reversed()  {
        for j in (0..<n).reversed()  {
            dp[i][j] = dp[i+1][j] + dp[i][j+1]
        }
    }
    return dp[0][0]
    */
    //空间优化O(N)
    var dp = [Int](repeating: 1, count: n + 1)
    for _ in (0..<m-1).reversed()  {//从倒数第二行开始
        for j in (0..<n-1).reversed()  {//从倒数第二列开始
            dp[j] = dp[j] + dp[j+1]
        }
    }
    return dp[0]

}
//print(uniquePaths(7,3))

//https://leetcode-cn.com/problems/unique-paths/solution/swift-zi-ding-xiang-xia-de-di-gui-shen-du-you-xi-2/
//自顶向下的递归，深度优先搜索，缓存已经被计算的值,终止条件最低边和最右边返回1
//执行用时：8 ms, 在所有 Swift 提交中击败了63.64%的用户
//内存消耗：20.8 MB, 在所有 Swift 提交中击败了41.86%的用户
func uniquePaths_a(_ m: Int, _ n: Int) -> Int {
    var cache =  Dictionary<String, Int>()
    func dfs(_ i: Int, _ j: Int) -> Int {
        if i == m - 1 || j == n - 1 {
            return 1
        }
        if let item = cache["\(i)-\(j)"] {
            return item
        }
        let res = dfs(i+1,j) + dfs(i,j+1)
        cache["\(i)-\(j)"] = res
        return res
    }
    return dfs(0,0)
}
//print(uniquePaths_a(7,3))
```

### [unique-paths-ii](https://leetcode-cn.com/problems/unique-paths-ii/)

> 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

```swift
//https://leetcode-cn.com/problems/unique-paths-ii/solution/swift-dong-tai-gui-hua-zi-di-xiang-shang-kong-ji-4/
//动态规划（自底向上），空间优化O(N)
//执行用时：24 ms, 在所有 Swift 提交中击败了40.23%的用户
//内存消耗：20.8 MB, 在所有 Swift 提交中击败了76.92%的用户
func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
    let m = obstacleGrid.count
    guard m != 0 else{
        return 0
    }
    let n = obstacleGrid[0].count
    /*
     var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
     dp[m][n-1] =  1 //主要是处理最底部一行和最右边的一列
     for i in (0..<m).reversed()  {
     for j in (0..<n).reversed()  {
     if(obstacleGrid[i][j] == 1){
     dp[i][j] = 0
     }else{
     dp[i][j] = dp[i+1][j] + dp[i][j+1]
     }
     }
     }
     return dp[0][0]
     */
    //    空间优化O(N)
    var dp = [Int](repeating: 0, count: n + 1)
    dp[n-1] = 1
    for i in (0..<m).reversed()  {
        for j in (0..<n).reversed()  {
            if(obstacleGrid[i][j] == 1){
                dp[j] = 0
            }else{
                dp[j] = dp[j] + dp[j+1]
            }
        }
    }
    return dp[0]
}

//https://leetcode-cn.com/problems/unique-paths-ii/solution/swift-di-gui-shi-xian-you-hua-huan-cun-liang-chong/
//版本：swift5
//递归实现，优化缓存，两种结束条件
//执行用时：20 ms, 在所有 Swift 提交中击败了82.76%的用户
//内存消耗：21 MB, 在所有 Swift 提交中击败了15.38%的用户
func uniquePathsWithObstacles_a(_ obstacleGrid: [[Int]]) -> Int {
    let m = obstacleGrid.count
    guard m != 0 else{
        return 0
    }
    let n = obstacleGrid[0].count

    var cache =  Dictionary<String, Int>()
    func dfs(_ i: Int, _ j: Int) -> Int {
        if i > m - 1 || j > n - 1 || obstacleGrid[i][j] == 1{
            return 0
        }
        if i == m - 1 && j == n - 1 {
            return 1
        }
        if let item = cache["\(i)-\(j)"] {
            return item
        }
        let res = dfs(i+1,j) + dfs(i,j+1)
        cache["\(i)-\(j)"] = res
        return res
    }
    return dfs(0,0)
}
```

## 2、序列类型（40%）

### [climbing-stairs](https://leetcode-cn.com/problems/climbing-stairs/)

> 假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。

```swift
//https://leetcode-cn.com/problems/climbing-stairs/solution/swift-dong-tai-gui-hua-fxfx-1fx-2-by-hu-cheng-he-d/
//动态规划：f(x)=f(x−1)+f(x−2)
//执行用时：4 ms, 在所有 Swift 提交中击败了84.08%的用户
//内存消耗：20.7 MB, 在所有 Swift 提交中击败了64.71%的用户
func climbStairs(_ n: Int) -> Int {//n是正整数
    var x1 = 0,x2 = 1 ,x3 = 0
    for _ in 1...n {
        x3 = x1 + x2
        x1 = x2
        x2 = x3
    }
    return x3
}

//https://leetcode-cn.com/problems/climbing-stairs/solution/swift-di-gui-fxfx-1fx-2-by-hu-cheng-he-da-bai-sha/
//递归：f(x)=f(x−1)+f(x−2)
//执行用时：4 ms, 在所有 Swift 提交中击败了84.17%的用户
//内存消耗：20.7 MB, 在所有 Swift 提交中击败了64.91%的用户
func climbStairs_a(_ n: Int) -> Int {//n是正整数
    var cache = [Int](repeating: 0, count: n+1)
    func dfs(_ n: Int) -> Int{
        if cache[n] != 0 {
            return cache[n]
        }
        if n <= 2 {
            return n
        }
//        cache[n - 1] = dfs(n - 1)
//        cache[n - 2] = dfs(n - 2)
//        return cache[n - 1] +  cache[n - 2]
        cache[n] = dfs(n - 1) +  dfs(n - 2)
        return cache[n]
    }
    return dfs(n)
}
```

### [jump-game](https://leetcode-cn.com/problems/jump-game/)

> 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。

```swift
//https://leetcode-cn.com/problems/jump-game/solution/swift-dong-tai-gui-hua-cong-qian-wang-hou-by-hu-ch/
//从前往后
//执行用时：80 ms, 在所有 Swift 提交中击败了88.08%的用户
//内存消耗：20.8 MB, 在所有 Swift 提交中击败了84.00%的用户
func canJump(_ nums: [Int]) -> Bool {
    let count = nums.count
    var distance = 0
    for i in 0..<count {
        guard i <= distance else{
            return false
        }
        distance = max(distance,nums[i]+i)
        if distance >= count - 1 {
            return true
        }
    }
    return true
}

//https://leetcode-cn.com/problems/jump-game/solution/swift-dong-tai-gui-hua-cong-hou-wang-qian-pan-duan/
//动态规划：从后往前判断
//执行用时：76 ms, 在所有 Swift 提交中击败了95.92%的用户
//内存消耗：21 MB, 在所有 Swift 提交中击败了23.81%的用户
func canJump_a(_ nums: [Int]) -> Bool {
    let count = nums.count
    var endIndex = count - 1
    for i in (0..<count-1).reversed() {
        if i + nums[i] >= endIndex{
            endIndex = min(endIndex,i)
        }
    }
    return endIndex == 0
}
```

### [jump-game-ii](https://leetcode-cn.com/problems/jump-game-ii/)

> 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

```swift
//https://leetcode-cn.com/problems/jump-game-ii/solution/swift-zheng-xiang-dong-tai-cha-zhao-by-hu-cheng-he/
//正向动态查找
//执行用时：84 ms, 在所有 Swift 提交中击败了74.23%的用户
//内存消耗：21 MB, 在所有 Swift 提交中击败了46.15%的用户
func jump(_ nums: [Int]) -> Int {
    let count = nums.count
    var maxPosition = 0
    var step = 0
    var end = 0
    for i in 0..<(count - 1) {
        maxPosition = max(maxPosition,nums[i]+i)
        if i == end{
            end = maxPosition
            step += 1
        }
        //优化：提前结束
        if maxPosition >= count - 1{
            if end < count - 1{
                step += 1
            }
            break
        }
    }
    return step
}
```

### [palindrome-partitioning-ii](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)

> 给定一个字符串 *s*，将 *s* 分割成一些子串，使每个子串都是回文串。 返回符合要求的最少分割次数。

```swift
//https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/swift-dong-tai-gui-hua-ti-qian-huan-cun-hui-wen-ch/
//动态规划，提前缓存回文串
//执行用时：116 ms, 在所有 Swift 提交中击败了100.00%的用户
//内存消耗：21.6 MB, 在所有 Swift 提交中击败了50.00%的用户
func minCut(_ s: String) -> Int {
    let count = s.count

    if count <= 1{
        return 0
    }

    var dp = Array(0..<count)

    let sArray = Array(s)

    var checkPalindrome = Array(repeating: Array(repeating: false, count: count), count: count)
    for right in 0..<count {
        for left in 0...right {
            if sArray[left] == sArray[right] && ( right - left <= 2 || checkPalindrome[left + 1][right - 1] == true) {//0,1,2距离的都可以直接判断
                checkPalindrome[left][right] = true
            }
        }
    }

    for right in 0..<count {
        if checkPalindrome[0][right] {
            dp[right] = 0
            continue
        }
        for left in 0..<right {
            if checkPalindrome[left + 1][right] {
                dp[right] = min(dp[right], dp[left] + 1);
            }
        }
    }
    return dp[count - 1]
}
```

注意点

* 判断回文字符串时，可以提前用动态规划算好，减少时间复杂度

### [longest-increasing-subsequence](https://leetcode-cn.com/problems/longest-increasing-subsequence/)

> 给定一个无序的整数数组，找到其中最长上升子序列的长度。

```swift
//https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/swift-dong-tai-gui-hua-by-hu-cheng-he-da-bai-sha-3/
//执行用时：140 ms, 在所有 Swift 提交中击败了37.38%的用户
//内存消耗：20.6 MB, 在所有 Swift 提交中击败了78.79%的用户
func lengthOfLIS(_ nums: [Int]) -> Int {
    let count = nums.count
    if count <= 1 {
        return count
    }
    var dp = Array(repeating: 1, count: count)
    var res = 1;
    for i in 1..<count {
        for j in 0..<i {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i],dp[j] + 1)
            }
        }
        res = max(res,dp[i])
    }
    return res
}
```

### [word-break](https://leetcode-cn.com/problems/word-break/)

> 给定一个**非空**字符串 *s* 和一个包含**非空**单词列表的字典 *wordDict*，判定 *s* 是否可以被空格拆分为一个或多个在字典中出现的单词。

```swift
//https://leetcode-cn.com/problems/word-break/solution/swift-dong-tai-gui-hua-you-hua-bian-li-chang-du-by/
//执行用时：16 ms, 在所有 Swift 提交中击败了94.96%的用户
//内存消耗：14.3 MB, 在所有 Swift 提交中击败了100.00%的用户
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    var wordSet = Set<String>()
    var maxCount = 0
    var minCount = Int.max
    for item in wordDict {
        wordSet.insert(item)
        maxCount = max(item.count ,maxCount)
        minCount = min(item.count ,minCount)
    }


    let dpCount = s.count + 1
    var dp = Array(repeating: false, count: dpCount)
    dp[0] = true

    for i in 1..<dpCount {
        let left = max( i - maxCount ,0)
        let right = (i - minCount)
        if left > right{
            continue
        }
        for j in left...right {
            //        for j in 0..<i {
            //            if i - j < minCount {
            //                break;
            //            }
            //            if i - j > maxCount {
            //                continue;
            //            }
            let start = s.index(s.startIndex, offsetBy: j)
            let end = s.index(s.startIndex, offsetBy: i)
            let subStr = s[start..<end]
            if wordSet.contains(String(subStr)) && dp[j]{
                dp[i] = true
                break
            }
        }
    }

    return dp[dpCount-1]
}
//print(wordBreak("applepenapple",["apple","pen"]))

//https://leetcode-cn.com/problems/word-break/solution/swift-ji-yi-hua-hui-su-by-hu-cheng-he-da-bai-sha/
//执行用时：16 ms, 在所有 Swift 提交中击败了94.96%的用户
//内存消耗：14.1 MB, 在所有 Swift 提交中击败了100.00%的用户
func wordBreak_a(_ s: String, _ wordDict: [String]) -> Bool {
    var cache = [String:Bool]()
    func check(_ str: String) -> Bool{
        guard str.count > 0 else{
            return true
        }
        if let temp = cache[str]{
            return temp
        }
        var flag = false
        for word in wordDict {
            if(str.hasPrefix(word)){
                if check(String(str.suffix(str.count - word.count))) {
                    flag = true
                    break
                }
            }
        }
        cache[str] = flag
        return flag

    }
    return check(s)
}

//print(wordBreak_a("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]))
```

小结

常见处理方式是给 0 位置占位，这样处理问题时一视同仁，初始化则在原来基础上 length+1，返回结果 f\[n]

* 状态可以为前 i 个
* 初始化 length+1
* 取值 index=i-1
* 返回值：f\[n]或者 f\[m]\[n]

## Two Sequences DP（40%）

### [longest-common-subsequence](https://leetcode-cn.com/problems/longest-common-subsequence/)

> 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

```swift
//https://leetcode-cn.com/problems/longest-common-subsequence/solution/swift-dong-tai-gui-hua-biao-by-hu-cheng-he-da-bai-/
//执行用时：84 ms, 在所有 Swift 提交中击败了60.58%的用户
//内存消耗：21.5 MB, 在所有 Swift 提交中击败了69.77%的用户
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
    let array1 = Array(text1)
    let array2 = Array(text2)

    var dp = Array(repeating: Array(repeating: 0, count: array2.count + 1), count: array1.count + 1)

    for i in 1...array1.count {
        for j in 1...array2.count {
            if array1[i - 1] == array2[j - 1]{
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j] ,dp[i][j-1])
            }
        }
    }

    return dp[array1.count][array2.count]
}

//print(longestCommonSubsequence("abc","def"))
```

### [edit-distance](https://leetcode-cn.com/problems/edit-distance/)

> 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数\
> 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符

思路：和上题很类似，相等则不需要操作，否则取删除、插入、替换最小操作次数的值+1

```swift
//https://leetcode-cn.com/problems/edit-distance/solution/swift-dong-tai-gui-hua-by-hu-cheng-he-da-bai-sha-4/
//执行用时：52 ms, 在所有 Swift 提交中击败了86.67%的用户
//内存消耗：15.9 MB, 在所有 Swift 提交中击败了100.00%的用户
func minDistance(_ word1: String, _ word2: String) -> Int {
    let array1 = Array(word1)
    let array2 = Array(word2)

    if array1.count == 0 || array2.count == 0 {
        return array1.count + array2.count
    }

    var dp = Array(repeating: Array(repeating: 0, count: array2.count + 1), count: array1.count + 1)
    for row in 0...array1.count {
        dp[row][0] = row
    }
    for column in 0...array2.count {
        dp[0][column] = column
    }

    for i in 1...array1.count {
        for j in 1...array2.count {
            if array1[i - 1] == array2[j - 1]{
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j] ,dp[i][j-1], dp[i-1][j-1])+1
            }
        }
    }

    return dp[array1.count][array2.count]
}
```

## 零钱和背包（10%）

### [coin-change](https://leetcode-cn.com/problems/coin-change/)

> 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

思路：和其他 DP 不太一样，i 表示钱或者容量

```swift
//https://leetcode-cn.com/problems/coin-change/solution/swift-dong-tai-gui-hua-by-hu-cheng-he-da-bai-sha-5/
//执行用时：824 ms, 在所有 Swift 提交中击败了65.87%的用户
//内存消耗：13.7 MB, 在所有 Swift 提交中击败了97.26%的用户
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    if(amount == 0){
        return 0
    }

    var dp = Array(repeating: amount + 1, count: amount + 1)
    dp[0] = 0

    for money in 1...amount {
        for coin in coins {
            if money - coin >= 0 {
                dp[money] = min(dp[money],dp[money - coin] + 1)
            }
        }
    }

    return  (dp[amount] == amount + 1) ? -1 : dp[amount]
}
//print(coinChange([2],3))
```

注意

> dp\[i-a\[j]] 决策 a\[j]是否参与

### [backpack](https://www.lintcode.com/problem/backpack/description)

> 在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为 m，每个物品的大小为 A\[i]

```swift
func backPack (_ A: [Int], _ m: Int)-> Int {
    // write your code here
    // f[i][j] 前i个物品，是否能装j
    // f[i][j] =f[i-1][j] f[i-1][j-a[i] j>a[i]
    // f[0][0]=true f[...][0]=true
    // f[n][X]
    var f = Array(repeating: Array(repeating: false, count: m + 1), count: A.count + 1)
    f[0][0]=true

    for i in 1...A.count {
        for j in 0...m {
            f[i][j]=f[i-1][j]
            if j - A[i-1] >= 0 && f[i-1][j - A[i-1]] {
                f[i][j]=true
            }

        }
    }

    for i in (0...m).reversed() {
        if f[A.count][i] {
            return i
        }
    }
    return 0
}
//print(backPack([2,3,5,7],12))
//print(backPack([3,4,8,5],10))
```

### [backpack-ii](https://www.lintcode.com/problem/backpack-ii/description)

> 有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值. 问最多能装入背包的总价值是多大?

思路：f\[i]\[j] 前 i 个物品，装入 j 背包 最大价值

```swift
func backPackII (_ m: Int,_ A: [Int],_ V: [Int])-> Int {
    // write your code here
    // f[i][j] 前i个物品，装入j背包 最大价值
    // f[i][j] =max(f[i-1][j] ,f[i-1][j-A[i]]+V[i]) 是否加入A[i]物品
    // f[0][0]=0 f[0][...]=0 f[...][0]=0
    var f = Array(repeating: Array(repeating: 0, count: m + 1), count: A.count + 1)

    for i in 1...A.count {
        for j in 0...m {
            f[i][j]=f[i-1][j]
            if j - A[i-1] >= 0  {
                f[i][j] = max(f[i-1][j], f[i-1][j - A[i-1]]+V[i-1])
            }

        }
    }

    return f[A.count][m]
}

print(backPackII(10,[2, 3, 5, 7],[1, 5, 2, 4]))
print(backPackII(10,[2, 3, 8],[2, 5, 8]))
```

## 练习

Matrix DP (10%)

* [ ] [triangle](https://leetcode-cn.com/problems/triangle/)
* [ ] [minimum-path-sum](https://leetcode-cn.com/problems/minimum-path-sum/)
* [ ] [unique-paths](https://leetcode-cn.com/problems/unique-paths/)
* [ ] [unique-paths-ii](https://leetcode-cn.com/problems/unique-paths-ii/)

Sequence (40%)

* [ ] [climbing-stairs](https://leetcode-cn.com/problems/climbing-stairs/)
* [ ] [jump-game](https://leetcode-cn.com/problems/jump-game/)
* [ ] [jump-game-ii](https://leetcode-cn.com/problems/jump-game-ii/)
* [ ] [palindrome-partitioning-ii](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)
* [ ] [longest-increasing-subsequence](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
* [ ] [word-break](https://leetcode-cn.com/problems/word-break/)

Two Sequences DP (40%)

* [ ] [longest-common-subsequence](https://leetcode-cn.com/problems/longest-common-subsequence/)
* [ ] [edit-distance](https://leetcode-cn.com/problems/edit-distance/)

Backpack & Coin Change (10%)

* [ ] [coin-change](https://leetcode-cn.com/problems/coin-change/)
* [ ] [backpack](https://www.lintcode.com/problem/backpack/description)
* [ ] [backpack-ii](https://www.lintcode.com/problem/backpack-ii/description)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://zyj.gitbook.io/algorithm-pattern-swift/ji-chu-suan-fa-pian/dp.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.