一、概述

动态规划程序设计是解决多阶段决策过程最优化问题的一种途径。动态规划的设计方法对不同的问题，有各具特色的解题方法，不存在一种万能的动态规划算法，可以解决各种最优化问题。需要满足“最优子结构”和“无后效性”的两项基本条件。

动态规划的解题步骤：

1. 确定状态：状态是一个数学形式；
2. 确定状态转移方程和边界条件：递归或递推；
3. 程序实现。

动态规划大致可以分为以下几类：线性、区间、背包、树型、数位、状态压缩等。常见的问题有“最长不下降子序列”、“最长公共子序列”等。

二、最长不下降子序列

有一个长为 n 的数列 a1, a2, ......, an。请求出这个序列中最长不下降子序列的长度。不下降子序列指的是对于任意的 i<j 都满足 ai<=aj 的子序列，该问题被称为最长不下降子序列（LIS，Longest Increasing Subsequence）。

举个例子：给你一个序列为（1，5，2，6，9，10，3，15，1），那么它的最长不下降子序列为：（1，2，6，9，10，15）

输入格式

• 第一行一个整数 n
• 第二行输入 n 个数

输出格式

• 最长不下降子序列的长度

样例输入

9
1 5 2 6 9 10 3 15 1

样例输出

6

思路

1. 定义一个 dp[]数组，dp[i]用来表示以 a[i]作为结尾的序列的最长不下降子长度；
2. 确定状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，条件是 j<i && a[j] <= a[i]；
3. 确定边界：i=1 时：dp[1] = 1。

三、01 背包

有一位国王有 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如：有的黄金储量是 500kg 黄金，需要 5 个工人来挖掘，有的黄金储量是 200kg，需要 3 个工人来挖掘。如果参与挖掘的工人总数是 10。每座金矿要么全挖，要么不挖，不能派一半的人挖一半的金矿。要求用程序求出，想得到尽可能多的黄金，应该选择挖取哪几座金矿？

输入格式

• 第一行为两个正整数，第一个整数表示金矿的数量 n(n<=100)，第二个整数表示参与挖掘的工人总数为 m(m<=100)。
• 之后有 n 行，每行有两个正整数，依次为每个金矿的储量以及挖矿需要的工人数。

输出格式

• 一个整数，最多能挖的黄金数量。

样例输入

5 10
200 3
300 4
350 3
400 5
500 5

样例输出

900

思路

1. 定义一个 dp数组，dp[i]表示 i 个工人最多能挖的黄金数量；
2. 确定状态转移方程：dp[j] = max(dp[j], dp[j - w[i]] + v[i])，挖或者不挖此金矿，更新最大能挖的黄金数量；
3. 输出：dp[m]，表示 m 个工人最多能挖的黄金数量。

四、训练题

1. 动态规划的两大基本条件是()。

{{ select(1) }}

• 最优子结构和无后效性
• 最优子结构和当前最优解
• 当前最优解和无后效性
• 划分区间和无后效性

2. 下列哪个选项不是动态规划的特征()。

{{ select(2) }}

• 大问题可分解性
• 子问题易解决性
• 子问题不重叠性
• 解可合并性

3. 以下哪个问题不适用于动态规划解决()。

{{ select(3) }}

• 最长公共子序列
• 最长不下降子序列
• 背包问题
• 排队问题

4. 动态规划和贪心算法的区别不包含()。

{{ select(4) }}

• 贪心算法每一步的最优解一定包含上一步的最优解，动态规划全局最优解中不一定包含前一个局部最优解。
• 贪心不能保证最后解是最佳的；而动态规划本质是穷举法，可以保证结果是最佳的。
• 一旦证明某问题的贪心选择性质，用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。
• 动态规划划分子结构，贪心算法不划分。

5. 解决 01 背包问题时，有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使得总价值最大。此问题的动态规划转移方程是( )。（j 表示体积，i 表示第 i 件物品）

{{ select(5) }}

• dp[j] = max(dp[i], dp[j - w[i]] + v[i])
• dp[i] = max(dp[j], dp[j - w[i]] + v[i])
• dp[j] = max(dp[j], dp[j - w[i]] + v[i])
• dp[j] = max(dp[j], dp[j - w[j]] + v[j])