【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)

简介: 【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总

介绍  

定义  

动态规划时一种运筹学方法,是在多轮决策过程中的最优方法。

应用场景  

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。

核心  

求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。

动态规划特点(三要素)  

1.最优子结构:原问题的最优解所包含的子问题的解也是最优的,通过子问题的最值得到原问题的最值。

2.存在重叠子问题:子问题间不独立(这是动态规划区别于分治的最大不同);如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算

3.无后效性:即后续的结果不会影响当前结果。

通常的思考过程  

动态规划没有标准的解题方法,但在宏观上有通用的方法论:

下面的 k 表示多轮决策的第 k 轮

1.分阶段,将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段,它们可以是不满足独立性的。    

2.找状态,选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变,更像是决策可能的结果。

3.做决策,确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作,例如 D2 的可能的决策动作是 D2 -> E2 和 D2 -> E3。

4.状态转移方程。这个步骤是动态规划最重要的核心,即 sk+1= uk(sk) 。

5.定目标。写出代表多轮决策目标的指标函数 Vk,n。

6.寻找终止条件。

状态转移方程一般过程  

状态转移方程:一般思考过程,明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。方程本质是数学的递推式

解题方法  

递归是一种自顶向下的求解方式,DP数组是一种自底向上的求解方式。

1.递归寻找暴力解:自顶向下求解;

2.通过备忘录memo优化递归过程,剔除重复计算,消除一下重叠子问题;

3.通过DP table 自底向上求解:主要是需要明确DP数组的含义定义,然后通过递推进行推导。

DP数组注意事项  

数组的遍历方向

# 正向遍历
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)        
    for (int j = 0; j < n; j++)
        // 计算 dp[i][j]
# 反向遍历
for (int i = m - 1; i >= 0; i--)
    for (int j = n - 1; j >= 0; j--)
        // 计算 dp[i][j]
# 斜向遍历
for (int l = 2; l <= n; l++)
    for (int i = 0; i <= n - l; i++)
        int j = l + i - 1;
        // 计算 dp[i][j]

         

DP数组的递推计算过程需要注意两点:

1、遍历的过程中,所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置

主要就是看 base case 和最终结果的存储位置。

如:编辑距离问题:正向遍历    

回文子序列问题:从左至右斜着遍历,或从下向上从左到右遍历,都可以

   

举例  

1.斐波拉契数列  

暴力递归:时间复杂度2^n指数级  

def fib(n):
    if n <= 2:
        return 1
    return fib(n-1) + fib(n-2)

带备忘录的递归  

def fib(n):
    def helper(n):
        if n <= 2:
            return 1
        if n in memo:
            return memo[n]
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]
    memo = {} # 记录已经计算过的值,防止重复计算
    return helper(n)

DP数组的迭代解法  

上述递归过程是自顶向下求解的,dp数组则是自底向上求解的。

def fib(n):
    dp = [0 for _ in range(n+1)]        
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

根据斐波那契数列的状态转移方程,当前状态只和之前的两个状态有关,其实并不需要那么长的一个 DP table 来存储所有的状态,只要想办法存储之前的两个状态就行了。所以,可以进一步优化,把空间复杂度降为 O(1):

def fib(n):
    if n <= 2:
        return 1
    prev = 1
    curr = 1
    for i in range(3,n+1):
        prev, curr = curr, prev + curr
    return curr

2.零钱兑换问题  

题目:给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。

状态转移方程:

# 伪码框架
def coinChange(coins: List[int], amount: int):        
    # 定义:要凑出金额 n,至少要 dp(n) 个硬币
    def dp(n):
        # 做选择,选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res
    # 我们要求的问题是 dp(amount)
    return dp(amount)

实际代码:

暴力解法  

def coinChange(coins, amount):
    def dp(n):
        # 函数定义为目标金额为n时,所需的最少硬币数量
        # base case
        # 目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值,所以初始化结果为正无穷
        res = float('inf')
        for coin in coins:
            subpro = dp(n-coin)
            if subpro == -1:
                # 子问题无解,跳过
                continue
            res = min(res, 1 + subpro)
        return res if res != float('inf') else -1
    return dp(amount)

带备忘录的递归  

def coinChange(coins, amount):        
    def dp(n):
        # 函数定义为目标金额为n时,所需的最少硬币数量
        # base case
        # 目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1
        if n == 0: return 0
        if n < 0: return -1
        if n in memo:
            return memo[n]
        # 求最小值,所以初始化结果为正无穷
        res = float('inf')
        for coin in coins:
            subpro = dp(n-coin)
            if subpro == -1:
                # 子问题无解,跳过
                continue
            res = min(res, 1 + subpro)
        memo[n] = res if res != float('inf') else -1
        return memo[n]
    memo = {}
    return dp(amount)

DP数组迭代解法  

dp[i] = x 表示,当目标金额为 i 时,至少需要 x 枚硬币。

def coinChange(coins, amount):
# 数组大小为 amount + 1,初始值也为 amount + 1
# 因为总的零钱个数不会超过amount,所以初始化amount + 1即可
    dp = [amount + 1 for _ in (amount + 1)]
    dp[0] = 0
    for i in range(len(dp)):
        #  内层 for循环,求解的是所有子问题 + 1 的最小值
        for coin in coins:
            # 子问题无解,跳过
            if i - coin < 0:
                continue
            dp[i] = min(dp[i],1+dp[i-coin])        
    if dp[amount] == amount + 1:
        return  -1
    else:
        return dp[amount]

注:dp 数组初始化为 amount + 1 呢,因为凑成 amount 金额的硬币数最多只可能等于 amount(全用 1 元面值的硬币),所以初始化为 amount + 1 就相当于初始化为正无穷,便于后续取最小值。

这个题目相当于是组合问题,每个硬币可以用多次,一共有多少种组合。

说明:前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点,那就是用前k的硬币凑齐金额i,要分为两种情况开率,一种是没有用前k-1个硬币就凑齐了,一种是前面已经凑到了i-k,现在就差第k个硬币了。

DP[i] = DP[i] + DP[i-k]:

式子右边的DP[i]表示不使用第K个金币的和为i的组合, DP[i-k]表示使用金币k的和为i的组合数。

         

第 39 题问的是所有的组合列表,需要知道每一个组合是什么?,应该使用 回溯算法 求解,并且存储每一个组合;

第 518 题问的是组合有多少种,而不是问具体的解。应该使用 动态规划 求解

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:        
        # 子问题:对于硬币从0到k,我们必须使用第k个硬币的时候,当前金额的组合数
        # 状态数组DP[i]表示对于第k个硬币能凑的组合数
        # 转移方程DP[i] = DP[i] + DP[i-k]
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for x in range(1, amount + 1):
                 if x < coin: continue   # coin不能大于amount
                dp[x] += dp[x - coin]
        return dp[amount]

这个题实际上是排列问题,因为顺序不同的话视为不同的组合。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)        
        dp[0] = 1
        for x in range(1, target + 1):
            for num in nums:
                if x < num:continue
                dp[x] += dp[x - num]
        return dp[target]

         

参考:

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/

总结:

518零钱兑换2是一个组合问题,DP先遍历零钱列表,再遍历amount金额数;

def change(coins,amount):
    # 求的是组合数
    dp = [0 for _ in range(amount+1)]
    dp[0] = 1
    for coin in coins:  # 枚举硬币
        for i in range(amount + 1):  # 枚举金额
            if i < coin: continue #coin不能大于amount
            dp[i] = dp[i] + dp[i - coin]
    return dp[amount]

         

377组合个数是一个排列问题, DP先遍历amount金额数,再遍历零钱列表。

def change(coins,amount):
    # 求的是排列数
    dp = [0 for _ in range(amount+1)]
    dp[0] = 1        
    for i in range(amount + 1):  # 枚举金额
        for coin in coins:  #枚举硬币
            if i < coin: continue #coin不能大于amount
            dp[i] = dp[i] + dp[i - coin]
    return dp[amount]

举例:

在LeetCode上有两道题目非常类似,分别是

70.爬楼梯  --排列问题

518. 零钱兑换 II  -- 组合问题

如果我们把每次可走步数/零钱面额限制为[1,2], 把楼梯高度/总金额限制为3. 那么这两道题目就可以抽象成"给定[1,2], 求组合成3的组合数和排列数"。

爬台阶问题通用模板

def climbStairs(n):
    # 爬台阶问题通用模板
    dp = [0 for _ in range(n + 1)]
    dp[0] = 1
    steps = [1,2,4,5]
    for i in range(n+1):
        for j in range(len(steps)):
            if i < steps[j]: continue # 台阶少于跨越的步数
            dp[i] = dp[i] + dp[i-steps[j]]
    return dp[n]

【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(2)https://developer.aliyun.com/article/1536619

相关文章
|
1月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
3月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
51 6
|
3月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。
|
5月前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
38 1
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
52 0
|
5月前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
30 0