动态规划

#LeetCode#算法#动态规划 2023-12-31

动态规划

题目

198. 打家劫舍 - 力扣（LeetCode）

70. 爬楼梯 - 力扣（LeetCode）

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

2466. 统计构造好字符串的方案数 - 力扣（LeetCode）

213. 打家劫舍 II - 力扣（LeetCode）

LeetCode 198

思路

我认为记忆化搜索就是回溯时剪枝，将已经搜索了的结果保留下来，当下次需要时直接返回，以达到缩小时间复杂度的意义。回溯递归是自顶向下的。

本题记忆化搜索的思路是，当我们计算过当前 i 之前的和时，不再递归下去，而是返回之前记录的结果。但需要注意的是，数组中的元素需要初始化为 -1（因为 0 <= nums[i] <= 400）。

我觉得从记忆化搜索到递推的过程，灵神讲的很巧妙：

• 递归 -> 循环
• dfs(i) -> array[i]
• 递归边界 -> 数组初始值

array[i] = max(array[i - 1], array[i - 2] + nums[i])

上式等价于：ans = max(dfs(i + 1), dfs(i + 2) + nums[i])

不难看出递推是自底向下的。

代码实现

记忆化搜索

func rob(nums []int) int {
    var n = len(nums)
    var ans int
    var memory = make([]int, n)
    for i := range memory{
        memory[i] = -1
    }

    var dfs func(int) int

    dfs = func(i int) int{
        if i >= n{
            return 0
        }

        if memory[i] != -1{
            return memory[i]
        }

        ans = max(dfs(i + 1), dfs(i + 2) + nums[i])
        memory[i] = ans
        return ans
    }
    dfs(0)
    return ans
}

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

-> 递推 array[i] = max(array[i - 1], array[i - 2] + nums[i])

func rob(nums []int) int {
    var n = len(nums)
    var ans = make([]int, n)

    if len(nums) == 1{
        return nums[0]
    }

    if len(nums) == 2{
        return max(nums[0], nums[1])
    }

    ans[0], ans[1] = nums[0], max(nums[0], nums[1])

    for i := 2; i < n; i++{
        ans[i] = max(ans[i - 1], ans[i - 2] + nums[i])
    }

    return ans[n - 1]
}

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

array[i + 2] = max(array[i + 1], array[i] + nums[i])

func rob(nums []int) int {
    var n = len(nums)
    var ans = make([]int, n + 2)

    for i := 0; i < n; i++{
        ans[i + 2] = max(ans[i+1], ans[i] + nums[i])
    }

    return ans[n + 1]
}

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

LeetCode 70

思路

这里的记忆化，记忆的是剩余阶数为 residual 所拥有登顶的路径数。 我们递归的去枚举搜索剩余阶数拥有的路径，然后将递归得到的路径加到记忆化的数组 memory 中。
memory[n] 即为所得答案。

按照上题的方法，转为递推为：memory[n] = memory[n - 1] + memory[n - 2]

代码实现

func climbStairs(n int) int {
    var memory = make([]int, n + 1)
    for i := range memory{
        memory[i] = -1
    }

    var dfs func(int) int

    dfs = func(residual int) int{
        if residual == 0{
            // 加一条路径
            return 1
        }
        if residual < 0{
            // 超过楼顶了
            return 0
        }

        if memory[residual] != -1{
            return memory[residual]
        }

        // 下一步走一个
        memory[residual] = dfs(residual - 1)
        
        // 下一步走俩
        memory[residual] += dfs(residual - 2)

        return memory[residual]
    }
    dfs(n)
    return memory[n]
}

-> 递推 memory[n] = memory[n - 1] + memory[n - 2]

func climbStairs(n int) int {
    var memory = make([]int, n)

    if n == 1{
        return 1
    }
    if n == 2{
        return 2
    }

    memory[0], memory[1] = 1, 2

    for i := 2; i < n; i++{
        memory[i] = memory[i - 2] + memory[i - 1]
    }

    return memory[n - 1]
}

-> memory[n + 2] = memory[n + 1] + memory[n]

func climbStairs(n int) int {
    var memory = make([]int, n + 2)

    memory[0], memory[1] = 0, 1

    for i := 0; i < n; i++{
        memory[i + 2] = memory[i + 1] + memory[i]
    }

    return memory[n + 1]
}

LeetCode 746

思路

记忆化搜索：从 0 开始，计算每一个下标登顶所需要的最小开销。然后比较下标 0 和 1 那个需要的开销最小，返回即可。

递推 -> memory[i] = min(memory[i - 1], memory[i - 2]) + cost[i]

代码实现

func minCostClimbingStairs(cost []int) int {
    var n = len(cost)
    var memory = make([]int, n)
    for i := range memory{
        memory[i] = -1
    }

    var dfs func(int) int

    dfs = func(i int) int{
        if i >= n{
            return 0
        }

        if memory[i] != -1{
            return memory[i]
        }

        memory[i] = min(dfs(i + 1), dfs(i + 2)) + cost[i]
        
        return memory[i]
    }

    dfs(0)
    return min(memory[0], memory[1])
}

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

递推

func minCostClimbingStairs(cost []int) int {
    var n = len(cost)
    var memory = make([]int, n)
    
    memory[0], memory[1] = cost[0], cost[1]

    for i := 2; i < n; i++{
        memory[i] = min(memory[i - 1], memory[i - 2]) + cost[i]
    }

    return min(memory[n - 1], memory[n - 2])
}

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

LeetCode 2466

思路

跟爬楼梯差不多。记忆化搜索会超时。

代码实现

记忆化搜索（超时）

func countGoodStrings(low int, high int, zero int, one int) int {
    var memory = make([]int, high + 1)
    for i := range memory{
        memory[i] = -1
    }

    var mod int = 1e9 + 7
    var dfs func(int) int

    dfs = func(i int) int{
        if i > high{
            return 0
        }

        if memory[i] != -1{
            return memory[i]
        }

        if i >= low{
            return dfs(i + zero) + dfs(i + one) + 1
        }

        memory[i] = dfs(i + zero) + dfs(i + one)

        return memory[i] % mod
    }
    dfs(0)

    return memory[0]
}

动态规划

func countGoodStrings(low int, high int, zero int, one int) int {
    var ans int
    var mod int = 1e9 + 7
    var memory = make([]int, high + 1)
    memory[0] = 1 // 空字符串可构造的初始值

    for i := 1; i <= high; i++{
        if i >= one{
            memory[i] = (memory[i] + memory[i - one]) % mod
        }
        if i >= zero{
            memory[i] = (memory[i] + memory[i - zero]) % mod
        }
        if i >= low{
            ans = (ans + memory[i]) % mod
        }
    }

    return ans
}

LeetCode 213

代码实现

func rob(nums []int) int {
    var n = len(nums)

    // 选 0 和不选 0
    return max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n))
}

func rob1(nums []int, start, end int) int{
    // 空间优化
    f0, f1 := 0, 0
	
    for i := start; i < end; i++{
        f0, f1 = f1, max(f0 + nums[i], f1)
    }

    return f1
}

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