Back

To Top

动态规划

Sep 19, 2023

动态规划

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

算法思想

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

算法特性

以下三个动态规划的性质可用于判断动态规划方法是否适用于给定的问题。

最优子结构：在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。
无后效性：无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
重叠子问题：在求解原问题的时候，我们往往需要依赖其子问题，子问题依赖其子子问题，甚至可能同时依赖多个子问题，因此子问题之间是有重叠关系的。

题目特征

特点	示例
特点一：计数	题目问：有多少种方法？有多少种走法？
特点二：最大值/最小值	题目问：某种选择的最大值是什么？完成任务的最小时间是什么？数组的最长子序列时什么？达到目标最少操作多少次？
特点三：可能性	题目问：是否有可能出现某种情况？是否有可能在游戏中胜出？是否可以取出 k 个数满足条件?

设计思路

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态 -> 决策 1 -> 决策 2 -> ... -> 决策 n -> 结束状态

划分阶段
确定状态和状态变量
确定决策并写出状态转移方程
寻找边界条件

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

分析最优解的性质，并刻画其结构特征
递归的定义最优解
以自底向上或自顶向下的记忆方式（备忘录法）计算出最优解
根据计算最优值时得到的消息，构造问题的最优解

解题套路：

明确状态
明确选择
明确 dp 函数/数组的定义
明确 base case

状态转移表法

状态转移方程法

dp[n] = dn[n - 1] + dp[n - 2]

具备三要素，确认边界条件，初始化状态，开始切菜：

dp[0] = 1
dp[1] = 1

const climbStairs = function (n) {
  const dp = []

  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

优化

const climbStairs = function (n) {
  let a1 = 1
  let a2 = 1

  for (let i = 2; i <= n; i++) {
    ;[a1, a2] = [a2, a1 + a2]
  }

  return a2
}

// weights 物品重量
// weights[i]  -> 第 i 件物品重量
// values 物品价值
// values[i] -> 第 i 件物品价值
// W 背包可承载重量
const knapsack = function (weights, values, W) {}

第一步：明确状态和选择

状态
- 背包的空余容量剩多少
- 可选择的物品还有哪些
选择
- 把这个物品装进背包
- 不把这个物品装进背包

// 初始化 base case
dp[0][0][...] = base;
// 进行状态转移
for(const 状态1 of 状态1的所有值) {
  for(const 状态2 of 状态2的所有值) {
    for(...) {
      dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...);
    }
  }
}

第二步：明确 dp 数组的定义

dp[i][w] 的含义为：对于前 i 个物品，当背包的容量为 w 时，可以装的最大价值是 dp[i]w

比如说，dp[3][5] = 6 的含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

根据此定义，还可得出：base case 为 dp[0].. = dp[..]0 = 0，我们想计算的结果是 dp[N]w

第三步：根据选择写出状态转移逻辑

const knapsack = function (weights, values, W) {
  let dp = new Array().fill();
  dp[0][..] = 0;
  dp[..][0] = 0;

  for(let i = 0; i < weights.length; i++) {
    for (let j = 0; j < W; j++) {
      dp[i][j] = max(把物品 i 装进背包, 不把物品 i 装进背包)
    }
  }

  return dp[weights.length][W]
}

在 W 的约束下，把物品 i 装进背包，最大价值是多少？
在 W 的约束下，不把物品 i 装进背包，最大价值是多少？
- 相当于把 i - 1 物品装进背包 dp[i - 1][w]

杨辉三角

算法思想归纳总结

	标准分治	动态规划	贪心算法
适用类型	通用问题	优化问题	优化问题
子问题结构	每个子问题不同	很多子问题重复	只有一个子问题
最有子结构	不需要	必须满足	必须满足
子问题数	全部子问题都要解决	全部子问题都要解决	只要解决一个子问题
子问题在最优解里	全部	部分	部分
选择与求解次序	先选择后解决子问题	先解决子问题后选择	先选择后解决子问题

动态规划

动态规划

算法思想

算法特性

题目特征

设计思路

状态转移表法

状态转移方程法

经典问题

斐波那契数列

最长公共子串

0-1 背包问题

杨辉三角

相关问题

算法思想归纳总结

参考资料