动态规划

什么是动态规划？

把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

动态规划的特点

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

经典问题

0-1 背包问题

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

基本思路

func knapsack(weight []int, w int) int {
    n := len(weight)
    dp := make([][]bool, n)
    // 默认值false
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, w+1)
    }
    // 第一行的数据要特殊处理，可以利用哨兵优化
    dp[0][0] = true
    if weight[0] < w {
        dp[0][weight[0]] = true
    }

    // 动态规划
    for i := 1; i < n; i++ { // 动态规划状态转移
        for j := 0; j <= w; j++ { // 不把第i个物品放入背包
            if dp[i-1][j] {
                dp[i][j] = dp[i-1][j]
            }
        }

        for j := 0; j <= w-weight[i]; j++ { // 把第i个物品放入背包
            if dp[i-1][j] {
                dp[i][j+weight[i]] = true
            }
        }
    }

    // 最大值
    for i := w; i >= 0; i-- {
        if dp[n-1][i] {
            return i
        }
    }
    return 0
}

2.优化空间

func knapsack(weight []int, w int) int {
    n := len(weight)
    dp := make([]bool, w+1)
    dp[0] = true
    if weight[0] < w {
        dp[weight[0]] = true
    }

    for i := 1; i < n; i++ {
        for j := w - weight[i]; j >= 0; j-- {
            if dp[j] {
                dp[j+weight[i]] = true
            }
        }
    }

    for i := w; i >= 0; i-- {
        if dp[i] {
            return i
        }
    }
    return 0
}

0-1 背包问题升级版

0-1 背包问题，只涉及背包重量和物品重量。现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

func knapsack3(weight, value []int, w int) int {
    // 初始化列表
    n := len(weight)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, w+1)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < w+1; j++ {
            dp[i][j] = -1
        }
    }

    // 初始填充
    dp[0][0] = 0
    if weight[0] <= w {
        dp[0][weight[0]] = value[0]
    }

    for i := 1; i < n; i++ { // 动态规划，状态转移

        for j := 0; j < w+1; j++ { // 不选择第i个物品
            if dp[i-1][j] >= 0 {
                dp[i][j] = dp[i-1][j]
            }
        }

        for j := 0; j <= w-weight[i]; j++ {// 选择第i个物品
            if dp[i-1][j] >= 0 {
                v := dp[i-1][j] + value[i]
                if v > dp[i][j+weight[i]] {
                    dp[i][j+weight[i]] = v
                }
            }
        }
    }

    maxValue := -1
    for i := w; i >= 0; i-- {
        if dp[n-1][i] > maxValue {
            maxValue = dp[n-1][i]
        }
    }
    return maxValue
}