前言

本文本来为开放性实验报告，感觉有点小用所以打算作为浅学DP的笔记？（雾）ಥ_ಥ

首先是几个概念

动态规划思想

动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

动态规划重叠子问题

动态规划会将每个求解过的子问题的解记录下来，这样当下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。（虽然动态规划使用这种方式来提高计算效率，但不能说这种做法就是动态规划的核心）

动态规划最优化原理

无论过去的状态和决策如何，就所形成的状态而言，余下的诸策略必然构成一个最优子策略。

动态规划高效的原因

重叠子问题、记录子问题结果。

动态规划有效的原因

考虑了各种可能。

I.动态规划（线性）

1.数塔HDU-2084

问题描述

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

解题思路

由图片样例可得最佳路径为9-12-10-18-10 最大值为59

相比贪心与递归

a)贪心方法 如果是贪心从上至下分析 9-15-8-9-10 结果为51/实际最大值为59

b)递归方法 可以分析到最大值 但是需要2⁴次（广搜）/深搜（记忆化）复杂度进一步降低，但复杂度不如动态规划低

c)动态规划方法

​ 1)找子问题--> dp[i][j]:a[i][j]到第n层的最大值。

​ 2)自顶向下分析，自底向上求解。注意边界

​ 3)得到状态转移方程状态转移方程 dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1]);

2.最长公共子序列LCS

问题描述

给定两个序列A(a1,a2,a3…am)和B(b1, b2, b3…bn)，求长度最大的公共子序列的长度。

例如：1,5,2,6,8,7 和 2,3,5,6,9,8,4 的LCS为5,6,8（另一个解是2,6,8）

解题思路

先寻找子问题：设序列A=<a1, a2, …, ai>和B=<b1, b2, …, bj>的一个最长公共子序列C=。

设Ai-1=<a1, a2, …, ai-1>，Bj-1=<b1, b2, …, bj-1>，Ck-1=<c1, c2, …, ck-1>，则：

(1) ai=bj，则ck=ai=bj且Ck-1是Ai-1和Bj-1的最长公共子序列；

(2) ai≠bj, 则!(ck=ai=bj)，即：

┐(ck=ai ∧ ck=bj) Û ┐(ck=ai) Ú ┐(ck=bj) Û ck≠ai Ú ck≠bj

所以：

1) ai≠bj且ck≠ai ，则C是Ai-1和B的最长公共子序列；

2) ai≠bj且ck≠bj ，则C是A和Bj-1的最长公共子序列

得出状态转移方程：

dp[i][j]=dp[i-1][j-1]+1 (a[i]=b[j])

dp[i][j]=max{dp[i-1][j],dp[i][j-1]} (a[i]!=b[j])

dp[i][j]=0 (i==0或j==0)

II.背包问题

1.01背包-洛谷P1048[采药]

理解01背包是什么

给定一个背包(固定容量),装不同价值，不同容积的东西，总重量不能超过背包固定容量

问题描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例输入

70 3
71 100
69 1
1 2

样例输出

3

提示

【数据范围】

• 对于 $30\%$ 的数据，$M \le 10$；
• 对于全部的数据，$M \le 100$。

解题思路

设W[i]为重量，v[i]为价值

子问题：寻找dp[i][j]在j>=0的情况下最大

则状态转移方程为：dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);

一维数组优化：dp[c]=max(dp[c],dp[c-w[i]]+v[i]);(c为背包容量)

*注意 一维优化需要c初始应为背包最大容量

2.完全背包

问题描述

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

相比上一问增加无限制采药

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入

70 3
71 100
69 1
1 2

样例输出

140

数据规模与约定

• 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
• 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

解题思路

W[i]为重量，v[i]为价值

子问题：j>=0的情况下dp[i][j-k*w[i]]+k*v[i] 在j-k*w[i]>=0的同时dp[i][j-k*w[i]]+k*v[i]达到最大值

状态转移方程为：dp[i+1][j] = max{dp[i][j - k*w[i]] + k*v[i] | 0≤k≤j/w[i]}

一维数组优化： (c为背包容量) f[c]=max(f[c],f[c-w[i]]+v[i]); (c为背包容量)

注意：*与01背包相比在于只要背包没有装满就一直往背包中装同一物品，如果其他物品替换上一轮装的物品可以让背包总价值更高则把上一轮物品拿出装入这一轮物品知道装到不超过背包总容量下达到背包最大价值

3.多重背包

问题描述

有n种重量和价值分别为wi和vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。在这里，每种物品最多可以挑选Mi件。（i从0开始）

方法类似完全背包

解题思路

子问题：Mi<=j的情况下使得dp[i][j - k*w[i]] + k*v[i]达到最大

dp[i+1][j]：从编号0~i个物品中选出总重量不超过j的物品时总价值的最大值。

状态转移方程：dp[0][j]=0

dp[i+1][j] = max{dp[i][j - k*w[i]] + k*v[i] | 0≤k≤Mi}

总结

   动态规划的思想：动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略  

动态规划中需要注意的问题

1.找子问题：最优子结构:全局最优解基于子问题的最优解，通过决策获得。

2.状态表示：状态是对子问题计算的总结，后面的计算可以直接使用这个结果，而无需考虑子问题求解过程对后面求解的影响。

3.状态的转移：状态之间的转移方式，一般表现为一个方程。

4.初始条件：最小子问题的解，边界值。

动态规划的时间复杂度

动态规划的时间复杂度分为两部分：状态计算的时间复杂度，每个状态的状态转移时间复杂度。

所有状态计算的时间复杂度为 O(a)，单个状态的状态转移时间复杂度为 O(b)，则整个动态规划的求解过程的时间复杂度就是O(ab)。

线性DP 的状态数就是 O(n)，状态转移的时间复杂度一般为O(1) 或者 O(n)，也有 O(log 2n) 的，可能利用二分枚举进行状态转移，比如最长单调子序列。

背包问题总结

1.01背包：对于每一个物品，可以选择要也可以不选择。

2.完全背包：对于每一个物品，可以不选择，也可以选择任意多个（体积需要小于V）

3.多重背包：与完全背包区别在于数量不是无限的