动态规划算法思路

在这片文章中,我们总结了动态规划的基本思路,大致就分为三种

此文章整理自CyC大佬,github地址:

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md#leetcode-%E9%A2%98%E8%A7%A3---%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

常见的背包问题

  • 组合问题
  • True、False问题
  • 最大最小问题

组合问题

377. 组合总和 Ⅳ

494. 目标和

518. 零钱兑换 II

True、False问题

139. 单词拆分

416. 分割等和子集

最大最小问题

474. 一和零

322. 零钱兑换

公式

组合问题公式

dp[i] += dp[i-num]

True、False问题公式

dp[i] = dp[i] or dp[i-num]

最大最小问题公式

dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

以上三组公式是解决对应问题的核心公式。

解题步骤

当然拿到问题后,需要做到以下几个步骤:

  1. 分析是否为背包问题。
  2. 是以上三种背包问题中的哪一种。
  3. 是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
  4. 如果是组合问题是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法,不需要考虑顺序又有对应的解法。

背包问题特征

给定一个targettarget可以是数字也可以是字符串,再给定一个数组numsnums中装的可能是数字,也可能是字符串,:能否使用nums中的元素做各种排列组合得到target

背包问题技巧

如果是0-1背包,即数组中的元素不可重复使用nums放在外循环target在内循环,且内循环倒序

for num in nums:
    for i in range(target, nums-1, -1):

如果是完全背包,即数组中的元素可重复使用nums放在外循环target在内循环。且内循环正序

for num in nums:
    for i in range(nums, target+1):

如果组合问题需考虑元素之间的顺序,需将target放在外循环,将nums放在内循环

for i in range(1, target+1):
    for num in nums:
您的支持将鼓励我继续创作!