动态规划大集合

发表于

动态规划

贪心、回溯、动态规划

核心思路

想要计算得到第 n 个值的多少？那么，以下几点是我们必须要做到的

a. 定义一个一维数组 —> 一般用dp来命名

b. 动态方程的设定 —> 题中的F(N) = F(N - 1) + F(N - 2)

c. 初始化数值 —> F(0) = 0和F(1) = 1

上述的 a、b 和 c 点就是动态规划思想的几个核心要素

动态规划四大解题步骤处理问题

步骤一：定义dp数组的含义

步骤二：定义状态转移方程

步骤三：初始化过程转移的初始值

步骤四：可优化点(可选)

步骤一：定义dp数组的含义

所以，dp无论是一维的还是二维的，要想清楚代表什么，一般来说代表的是截止到目前情况下的最优值

步骤二：定义状态转移方程

F(N) = F(N - 1) + F(N - 2)

步骤三：初始化过程转移的初始值

既然动态方程定义好了，是不是需要一个支点来撬动它进行不断的计算下去。

那么，这个支点就需要我们来初始定义，将动态方程激活，进行计算。

F(N - 1)

F(N - 2)

步骤四：可优化点(可选)

可优化的这里，最重要的会是dp数组这块，也会有不同问题不同的优化点

案例1：打家劫舍

https://leetcode-cn.com/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
1. 定义数组：偷窃金额 amt
2. 状态方程 dp[i] = max(dp[i-1], num[i-1]+dp[i-2])
3. 初始化 dp[0] = 0, dp[1] = num[0]
4. 优化 只需存储 dp[i] dp[i-1] dp[i-2] , 即 r y x
*/
func rob(nums []int) int {
    if nums == nil || len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    // 此时 nums 里 至少有2个元素
    r, x, y := 0, 0, 0
    for i:=1; len(nums) >= i; i++ {
        r = max(y, x + nums[i-1])
        x = y
        y = r
    }
    return r
}

func max(x, y int) int {
    if x > y {
        return x
    } else {
        return y
    }
}

image-20201104211700171

案例2： 不同路径

https://leetcode-cn.com/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

img

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右
    示例 2:

输入: m = 7, n = 3
输出: 28

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

go 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
1. 定义dp数组：到达(i,j)的路径数 dp[i][j]
2. 状态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 初始化 dp[0][0] = 1, dp[0][0...n] = 1, dp[0...n][0] = 1
4. 优化 二维数组 转化成一维数组，dp[i] = dp[i] + dp[i-1]
*/
func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for i:=0; i<n; i++ {
        dp[i] = 1
    }
    for i:=1; i<m; i++ {
        for j:=1; j<n; j++ {
            dp[j] = dp[j] + dp[j-1]
        }
    }

    return dp[n-1]
}

案例3：不同路径II

https://leetcode-cn.com/problems/unique-paths-ii/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

img

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右
    通过次数107,863提交次数291,643

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([]int, n)
    if obstacleGrid[0][0] == 0 {
        dp[0] = 1
    }
    for i:=0; i<m; i++ {
        for j:=0; j<n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0
                continue
            }
            if j-1 >= 0 && obstacleGrid[i][j-1] == 0 {
                dp[j] = dp[j] + dp[j-1]
            }
            
        }
    }

    return dp[n-1]
}

image-20201104231946444

案例4：打家劫舍 II

https://leetcode-cn.com/problems/house-robber-ii/

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

1
2
3
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

1
2
3
4
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

1
2
输入：nums = [0]
输出：0

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
1. 定义dp数组  金额dp
2. 状态转移方程  dp[i] = max(dp[i-1], nums[i] + dp[i-2])
3. 初始化 
   3.1 偷首不偷尾 dp[0] = 0, dp[1] = nums[0] 长度 len(nums)-1
   3.2 不偷首偷尾 dp[0] = 0, dp[1] = nums[1] 长度 len(nums)
4. 优化  只需存储 dp[i] dp[i-1] dp[i-2] , 即 r y x
*/
func rob(nums []int) int {
    if nums == nil || len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    // 此时 nums 里 至少有2个元素
    r1, r2, x, y := 0, 0, 0, 0
    for i:=1; i<=len(nums)-1; i++ {
        r1 = max(y, x + nums[i-1])
        x = y
        y = r1
    }
    x, y = 0, 0
    for i:=2; i<=len(nums); i++ {
        r2 = max(y, x + nums[i-1])
        x = y
        y = r2
    }
    return max(r1, r2)
}

func max(x, y int) int {
    if x > y {
        return x
    } else {
        return y
    }
}

image-20201104233421183

案例5：打家劫舍 III

https://leetcode-cn.com/problems/house-robber-iii/

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

 3
/ \

2 3
\ \
3 1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

 3
/ \

4 5
/ \ \
1 3 1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
通过次数73,129提交次数120,784

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    dp := postTrasval(root)
    return max(dp[0], dp[1])
}
 /*
1. 定义dp数组 dp[i]代表该节点及以下打最多的劫（拿到最多的钱）
2. 状态转移方程
根据我们每走到一个节点，都会有两种情况，那就是 偷(1) 与 不偷(0)。我们分开来讨论：
a. 用 dp[0] 代表不偷取该节点到目前为止拿到最多的钱，那么儿子节点偷不偷都ok。
所以： dp[0] = max(left[0], left[1]) + max(right[0], right[1])
b. 用 dp[1] 代表偷了该节点到目前为止拿到最多的钱，则儿子节点都不能被偷。
所以：dp[1] = value + left[0] + right[0] (value代表该节点的价值)
3. 初始化
该例子的初始化比较简单，就是当前树的形状为空的时候，直接返回dp[0, 0]
4. 优化
 */
func postTrasval(root *TreeNode) [2]int {
    var dp [2]int
	if root == nil {
		return dp
	}
    
    left := postTrasval(root.Left)
    right := postTrasval(root.Right)

    dp[0] = max(left[0], left[1]) + max(right[0], right[1])
    dp[1] = root.Val + left[0] + right[0]

    return dp
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

image-20201105001245595

案例6：股票的最大利润

https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
1. 定义dp数组  最大利润 dp
2. 状态转移方程 dp[i] = max(dp[i-1], prices[i]-minPrice),  minPrice是 i之前的最小价格
3. 初始化 dp[0] = 0
4. 优化 dp[i], dp[i-1] 即 r, x
*/
func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }

    x, r := 0, 0
    minPrice := prices[0]
    for i:=1; i<len(prices); i++ {
        r = max(x, prices[i]-minPrice)
        x = r
        minPrice = min(minPrice, prices[i])
    }

    return r
}

func max(x, y int) int {
    if x > y {
        return x
    } else {
        return y
    }
}
func min(x, y int) int {
    if x < y {
        return x
    } else {
        return y
    }
}

image-20201105181417316

案例7： 买卖股票的最佳时机 II

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }

    maxPro := 0
    for i:=1; i<len(prices); i++ {
        if (prices[i] - prices[i-1] > 0) {
            maxPro += prices[i] - prices[i-1]
        }
    }

    return maxPro
}

image-20201105184613939

案例8：买卖股票的最佳时机 III

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

go解法

1
2


案例9：买卖股票的最佳时机 IV

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

0 <= k <= 109
0 <= prices.length <= 104
0 <= prices[i] <= 1000