[数据结构与算法]动态规划面试宝典（极客时间）学习笔记

动态规划面试宝典（极客时间）学习笔记

局部最优解

? 贪心算法就是一种经典的求解“局部最优解”的算法

整体最优解

? 动态规划

重叠子问题与备忘录

由斐波那契数列引出的重叠子问题

int febnaci (int n){
    if(n=0){
        return 0;
    }
    if(n=1){
        return 1;
    }
    if(n>1){
        return febnaci(n-1)+febnaci(n-2);
    }
    return 0;//如果输入n有误，返回默认值
}
//由于涉及到递归，效率很低，重复计算了很多子问题，它是自顶向下的

? 所谓重叠子问题，就是在大问题求解过程中会重复求解小问题

? 通过备忘录来解决重叠子问题

? 从求解顺序上来解决这个问题。在处理每个大问题之前，必须要求解哪些小问题，将小问题的解存放于备忘录中。从而就可以逐步根据小问题得到大问题的解。

动态规划问题特征：

• 重叠子问题：在穷举过程中（通过递归），存在重复计算的现象；

• 无后效性：子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策影响；

• 最优子结构：子问题之间必须相互独立，或者后续的计算可以通过前面的状态推导出来。

  动态规划首要解决的是“最优解”问题（最大值和最小值），即从很多解决问题的方案中找到最优的那一个。而求最优解的问题核心是穷举，把一个大问题分解为多个子问题，然后递归的找到每个子问题的最优解。最后，通过算法将每个子问题的最优解进行组合，得出原问题的答案。

状态方程

• 初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此需要一个“原点”作为“计算”的开端
• 状态参数：找出子问题与原问题之间会发生变化的变量
• 状态存储：dp[i]=Math.min(dp[i-1],num[i]+dp[i-1])
• 决策与状态转移：改变状态，让状态不断逼近初始化状态的行为

经典的动态规划问题

• 求最优解（最大值和最小值）：从一系列方案中寻找最优解决方案
• 求方案总数：计算满足要求的解决方案的数量
• 求可行性（True或False）:确定 提出的问题是否存在可行性方案

代表性问题如下

1.背包问题

• 0-1 背包：每个物品最多要么选择1个，要么选择0个。因此称之为0-1背包。所有物品的数量k[i]都为1。
• 完全背包：每个物品的数量都是无限的。
• 多重背包：每个物品都有固定的数量，指定了k[i]。

无论0-1背包还是完全背包，其实都是多重背包的特例。

解题框架：

首先，确定初始化状态，当没有物品时，重量为0，重量为0时，物品数量也为0。

接着，确定状态参数，也就是会影响我们进行决策的变量：

• 背包内物品数量N在增加，它是一个变量
• 背包内还能装下的物品重量在减少，也是一个变量。

因此，当前背包内的物品数量N和背包还能装下的重量W就是这个动态规划问题的状态参数

接着，再看如何决策。由于每种物品的数量为k[i]，因此可以将同一种物品多次放入背包。**核心在于：**针对一种物品，需要考察拿不同数量的情况下的最优解，也就是针对当前物品，应放入多少件当前物品，价值最大。

最后，动态规划需要一个备忘录来加速算法。由于有两个状态参数，考虑使用二维数组来存储子问题的答案。将其命名为dp[tn] [rw]，它的含义是：背包容量还剩 rw时，放入前tn种物品时的最大价值。

通用的背包状态转移方程
$$DP(tn,rw)=DP(tn?1,rw),rw<w[tn]$$

$$DP(tn,rw)=max[DP(tn?1,rw?k?w[tn])+k?v[tn]],0<=k<=min(k[tn],rw/w[tn])$$

2.路径问题

路径问题是求解总方案数量的经典代表问题。

机器人移动路径问题，直接给出状态转移方程：

$$DP(i,j)=(DP[i?1][j]+DP[i][j?1])ifi!=0orj!=0$$

$$DP(i,j)=1,i=0andj=0$$

3.跳跃游戏

可行性的代表问题：跳跃游戏

**题目：**给出一个非负整数数组 A，你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。判断你是否能到达数组的最后一个位置。

示例1：

输入：A = [2, 3, 1, 1, 6]
输出： True
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

首先确定初始化状态 ,0这个位置可以初始化为True

接着确定状态参数，由于只有一个状态参数，因此可以使用一位数组DP[i]来表示能否从出发点到达位置i

最后确定状态转移与决策，想要知道能否到达位置i，就需要逐个看前面的位置，判定能否从位置i-1,i-2,i-3…跳到位置i上，然后再看i-1这个位置能否到达。

给出状态转移方程的定义：
$$DP[i]=True,i=0$$

$$DP[i]=(DP[j]=true)and(max(A[j]+j)>=i),i!=0andj<i$$
4.其他问题

除了上面提到的几类代表性问题，还有两类问题需要关注：子数组问题和子序列问题。