吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

算法基础 - 动态规划法

Posted at 2021-04-28Updated at 2021-04-28 算法  算法 数据结构 leetcode 

动态规划用于就解决包含重叠子问题的问题，其中每一个子问题的状态都是由上一个状态推导出来的。

# 基础

动态规划的一般步骤：

  • 确定dp数组和其下标的含义
  • 确定递推公式
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

# 实践

# 斐波那契数

斐波那契数

  • 动规，dp数组代表第i个数，和题目直接对应
1
2
3
4
5
6
7
8
9
10
11
12
func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

# 爬楼梯

爬楼梯

  • 动规，dp表示到第i级台阶可能的方法
1
2
3
4
5
6
7
8
9
10
11
12
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

# 使用最小花费爬楼梯

使用最小花费爬楼梯

  • 动规，dp表示到第i级台阶可能的方法，最后一步没有花费，取最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minCostClimbingStairs(cost []int) int {
    if len(cost) <= 1 {
        return 0
    }
    dp := make([]int, len(cost))
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i := 2; i < len(cost); i++ {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    }
    return min(dp[len(cost) - 1], dp[len(cost) - 2])
}

# 不同路径

不同路径

  • 动规，dp表示到第i,j可能的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := range dp[0] {
        dp[0][j] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }

    return dp[m - 1][n - 1]
}

# 不同路径 II

不同路径 II

  • 动规，dp表示到第i,j可能的路径，加入障碍物后，所以障碍物位置的路径变为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
        dp[0][j] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                continue
            }
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

# 整数拆分

整数拆分

  • 动规，dp表示i的最大面积，对于每个拆分的数i，从1开始遍历j到i-1，最大面积是 (i - j) * j 和 i - j 的最大面积 * j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func integerBreak(n int) int {
    dp := make([]int, n + 1)
    dp[2] = 1
    for i := 3; i <= n; i++ {
        for j := 1; j < i - 1; j++ {
            dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))

        }
    }
    return dp[n]
}

# 不同的二叉搜索树

不同的二叉搜索树

  • dp为节点数为i的二叉树数量，等于所有j-1和i-j的数量组合累加（相加==i-1，去除了根节点），dp[0]为空节点，也可以算作一种
1
2
3
4
5
6
7
8
9
10
func numTrees(n int) int {
    dp := make([]int, n + 1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp[n]
}

# 青蛙过河

青蛙过河

  • dp为能否到第i个石子上，并且上一步跳k个单位，限制条件是在i块石子上最多能跳i，如果石子间距离大于i则一定不能到达终点，并且上次跳跃距离一定满足k <= i，如果不满足则可以停止跳跃，避免冗余计算。

能否调到，i表示当前所在位置，k表示上一次跳跃的距离的石头上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n := len(stones)
dp := make([][]bool, n)
for i := range dp {
    dp[i] = make([]bool, n)
}
dp[0][0] = true
for i := 1; i < n; i++ {
    if stones[i]-stones[i-1] > i {
        return false
    }
}
for i := 1; i < n; i++ {
    for j := i - 1; j >= 0; j-- {
        k := stones[i] - stones[j]
        if k > j+1 {
            break
        }
        dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
        if i == n-1 && dp[i][k] {
            return true
        }
    }
}
return false

# 分割等和子集

分割等和子集

  • 01背包问题，背包容量是sum/2，商品价值和重量均为元素的数值，背包如何正好装满，说明找到了总和为sum/2的子集，元素不可重复
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
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func canPartition(nums []int) bool {
    sum := 0
    for _, n := range nums {
        sum += n
    }
    if sum % 2 == 1 {
        return false
    }
    target := sum / 2
    dp := make([]int, 10001)
    for i := 0; i < len(nums); i++ {
        for j := target; j >= nums[i]; j-- {
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        }
    }

    return dp[target] == target
}

# 最后一块石头的重量 II

最后一块石头的重量 II

  • 01背包，背包容量是sum/2，商品价值和重量均为石头的重量，如何装最大化价值的石头dp[target]，另一部分没装的就是sum - dp[target]，sum/2向下取正，sum > 2dp[target]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func lastStoneWeightII(stones []int) int {
    dp := make([]int, 15001)
    sum := 0
    for _, s := range stones {
        sum += s
    }
    target := sum / 2
    for i := 0; i < len(stones); i++ {
        for j := target; j >= stones[i]; j-- {
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        }
    }
    return sum - dp[target] - dp[target]
}

# 目标和

目标和

  • 01背包，加号的总和为x，要求x - (sum - x) = S，dp[j]表示装满容量为j的背包有dp[i]种方法，那么dp[j] += dp[j - nums[i]]就是把所有可能的方法都加起来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, n := range nums {
        sum += n
    }
    if target > sum {
        return 0
    }
    if (target + sum) % 2 == 1 {
        return 0
    }

    bagSize := (target + sum) / 2
    dp := make([]int , bagSize + 1)
    dp[0] = 1
    for i := 0; i < len(nums); i++ {
        for j := bagSize; j >= nums[i]; j-- {
            dp[j] += dp[j - nums[i]]
        }
    }
    return dp[bagSize]
}

Share 

 Previous post: 机器学习系统 4-4 - 召回 Next post: 算法基础 - 贪心法 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo