谈谈.动态规划|DynamicProgramming

动态规划 (Dynamic Programming，DP) 是运筹学的一个分支，是求解 决策过程 最优化 的过程。一般情况下，DP问题主要因素都有方向性和离散性.

设计方法

应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠，此外还要求无后效性。在此基础上，通过对子结构抽象出来的状态以设计状态转移方程，用来刻画一个子问题是如何通过其他子问题得到的。

在根据转移方程计算子问题的解时，我们往往建立一张动态规划表对结果进行保存，在下面的计算中以期直接查表取值。因此，这样的表具有备忘录性质，我们也常常称其为备忘录。

最优子结构

用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。

某个问题是否具有最优子结构性质，很大程度上决定着它是否适用于动态规划算法（当然，具有最优子结构性质也意味着可能适用与贪心法）。

使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解。因此，我们必须小心确保考察了最优解中用到的所有子问题。 这是至关重要的一步，这关系到备忘录中的值是否切实有效。

子问题重叠

局限性

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。

首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；

另外当变量的维数增大时，总的计算量及存贮量急剧增大。

因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”.

状态压缩

待更

经典实例一览

1. 最长公共子序列
2. 最优二叉检索树
3. 投资问题
4. 图像压缩算法

最长公共子序列| Longest Common Subsequence

已知序列$X=<x_1,x_2,...,x_m>$ 和 序列$Z=<z_1,z_2,...,z_k>$ ，如果存在严格递增的下标序列$<i_1,i_2,...,i_k>$ 使得对所有的$j=1,2,...,k$ 都有：$x_{i_j}=z_j$ ，即有：

$$<x_{i_1},x_{i_2},...,x_{i_k}>\;=\;<z_1,z_2,...,z_k>$$

则称$Z$ 是$X$ 的一个子序列。

如果序列$Z$ 既是$X$ 的子序列，也是另一个序列$Y$ 的子序列，则称$Z$ 是$X,Y$ 的公共子序列。

最长公共子序列问题 就是对于给定的序列$X,Y$ 要求找出它们的公共子序列中，元素个数最多的子序列。

算法分析

最容易想到的算法自然是暴力穷举法，我们只需把$X$ 的所有子序列都找出来，再与$Y$ 比较验证即可。然而对于长度是$m$ 的序列$X$ 来说，其子序列的个数为$2^m$，再逐一与$Y$ 比较又要花费$O(n)$ 的次数（如果$Y$ 的长度是$n$ ），因此穷举法的复杂度是指数级的$O(n2^m)$.

下面将思考利用动态规划法求解 LCS 问题。

规定$X_a$ 表示一个序列$X$ 的前$a$ 个连续的元素构成的子序列，我们称$X_a$ 为$X$ 的一个前缀。

从后往前思考，一个 LCS 问题的求解是否依赖于输入序列$X,Y$ 的前缀呢？

假设$X=<x_1,x_2,...,x_m>$ 和$Y=<y_1,y_2,...,y_n>$ 的一个 LCS 为$Z=<z_1,z_2,...,z_k>$，则有：

1. 当$x_m=y_n$ 时，$z_k=x_m=y_n$，并且有$Z_{k-1}$ 是$X_{m-1},Y_{n-1}$ 的 LCS；
2. 当$x_m\neq y_n$ 且$z_k=x_m$ 时，有$Z$ 是$X_{m-1},Y$ 的 LCS；
3. 当$x_m\neq y_n$ 且$z_k=y_n$ 时，有$Z$ 是$X,Y_{n-1}$ 的 LCS.

不难从上述定理看出，LCS 问题拥有最优子结构，即一个 LCS 问题的求解依赖于输入序列$X,Y$ 的前缀。并且通过以上三点，我们已经无形之中划归了子问题：

如下图所示，将序列$X$ 的某前缀下标$i$ 和序列$Y$ 的某前缀下标$j$ 作为状态量，则它们的 LCS 长度用$dp(i,j)$ 表示。

于是可总结出状态转移方程.

$$dp(i,j)=\begin{cases} 0,&i=0\text{ or }j=0\\ dp(i-1,j-1)+1,&i,j\gt0\text{ and }x_i=y_j\\ \max\{dp(i-1,j),dp(i,j-1)\},&i,j\gt0\text{ and }x_i\neq y_j \end{cases}$$

如果不仅想要求出 LCS 的长度，而是将 LCS 给出的话，在算法设计时还需要引入标记函数 以进行解的追踪。从状态转移方程对$dp(i,j)$ 的赋值可能性中，我们可以人为在选取某种可能时顺势保存下当时的选择。

这里我们规定标记函数为：

$$B(i,j)=\begin{cases} ↖,&dp(i,j)=dp(i-1,j-1)+1\\ ←,&dp(i,j)=dp(i,j-1)\\ ↑,&dp(i,j)=dp(i-1,j) \end{cases}$$

伪代码与实现

$$\begin{aligned} &\text{Algorithm: }\;\text{LCS}(X,Y)\\\\ 1.&\;m\leftarrow X.length\\ 2.&\;n\leftarrow Y.length\\ 3.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;m\;\mathbf{do}\;dp[i,0]\leftarrow0\\ 4.&\;\mathbf{for}\;j\;=1\;\mathbf{to}\;n\;\mathbf{do}\;dp[0,j]\leftarrow0\\ 5.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;m\;\mathbf{do}\\ 6.&\;\qquad\mathbf{for}\;j\;=1\;\mathbf{to}\;n\;\mathbf{do}\\ 7.&\;\qquad\qquad\mathbf{if}\;x_i=y_j\;\mathbf{then}\\ 8.&\;\qquad\qquad\qquad dp[i,j]\leftarrow dp[i-1,j-1]+1\\ 9.&\;\qquad\qquad\qquad B[i,j]\leftarrow 【↖】\\ 10.&\;\qquad\qquad\mathbf{else\;if}\;dp(i-1,j)\geq dp(i,j-1)\;\mathbf{then}\\ 11.&\;\qquad\qquad\qquad dp[i,j]\leftarrow dp[i-1,j]\\ 12.&\;\qquad\qquad\qquad B[i,j]\leftarrow 【↑】\\ 13.&\;\qquad\qquad\mathbf{else}\\ 14.&\;\qquad\qquad\qquad dp[i,j]\leftarrow dp[i,j-1]\\ 15.&\;\qquad\qquad\qquad B[i,j]\leftarrow 【←】\\ 16.&\;\mathbf{return}\;dp[m,n],B \end{aligned}$$

解的追溯将在下面的 c++ 实现中给出具体的递归调用实现。

分析伪代码可知，该算法的时间复杂度为$O(mn)$，空间复杂度为$O(mn)$.

以输入$X =<A, B, C, B, D, A, B> , Y = < B, D, C,A, B,A>$ 为例进行展示。

#define M 128

int dp[M][M];
int mark[M][M]; // 2代表↖，1代表 ↑，-1代表 ←

int Len(int p){
	// 计算灰度值的二进制位数
	int res = 0;
	while(p){
		res++;
		p = p/2;
	}
	return res;
}

int LCS(char X[], char Y[]){
	int m = strlen(X);
	int n = strlen(Y);
	memset(dp,0,sizeof(dp));
	memset(mark,0,sizeof(mark));
	for(int i = 1; i <= m; i++)
		dp[i][0] = 0;
	for(int j = 1; j <= n; j++)
		dp[0][j] = 0;
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(X[i-1] == Y[j-1]){ //数组下标是从0开始
				dp[i][j] = dp[i-1][j-1]+1;
				mark[i][j] = 2;
			}else if(dp[i-1][j] >= dp[i][j-1]){
				dp[i][j] = dp[i-1][j];
				mark[i][j] = 1;
			}else{
				dp[i][j] = dp[i][j-1];
				mark[i][j] = -1;
			}
		}
	}
	return dp[m][n];
}

void Traceback(char X[], int m, int n){
	// 追溯解
	if(mark[m][n] == 2){
		Traceback(X, m-1, n-1);
		cout << X[m-1] << " ";
	}else if(mark[m][n] == -1){
		Traceback(X, m, n-1);
	}else if(mark[m][n] == 1){
		Traceback(X, m-1, n);
	}else{
		return;
	}
}

int main(void){
	char A[] = "ABCBDAB";
	char B[] = "BDCABA";

	cout << "min Length = " << LCS(A,B) << endl << endl;
	Traceback(A, 7, 6);
	cout << "END" << endl;
    while(1);
}

最终的输出结果如下：

min Length = 4
B C B A

投资问题| Investment Problem

投资问题是运筹学和数学中一种很经典的数学规划模型。
其主要目的是考虑如何将有限的资金投入到若干个项目中，以获得最大的投资回报。具体描述如下：

假设拥有$m$ 元钱，可以对$n$ 个项目进行投资。将$x$ 元投入第$i$ 个项目所获得的收益记为$f_i(x)$. 要求给出一种决策，使得所得的收益最大。

可对该问题建立 非线性整数规划模型：

$$\begin{aligned} \max &\sum_{i=1}^nf_i(x_i)\\ s.t.&\begin{cases} \sum\limits_{i=1}^nx_i\leq m\\ x_i\in N,i=1,2,..,n \end{cases} \end{aligned}$$

式中，$x_i$ 表示对第$i$ 个项目投入的金额.

状态转移方程

思考本问题的输入，要求对给定金额$m$ 和前$n$ 个可选项目的投资问题给出最优解。
显然，$m,n$ 就是当前的状态量。最优解依靠当前状态给出，记为$dp(m,n)$.

从前向后思考.

1. 当金额为 1 ，可选项目为 1 时，显然将所有金额投入给该项目可获得最大收益，即$dp(1,1)=f_1(1)$.
   类似地，当金额为$x$，可选项目只有 1 时，$dp(x,1)=f_1(x)$.
2. 当金额为 2，可选项目为 2 时，可能的选择有：
   • 将 1 元投给项目 1，将 1 元投给项目 2；
   • 将全部 2 元都投给项目 1；
   • 将全部 2 元都投给项目 2.
     从以上可能中取最大则为最优解。
     即$dp(2,2)=\max\{dp(1,1)+f_2(1),dp(2,1)+f_2(0),dp(0,1)+f_2(2)\}$

依次类推，则可得到完整的状态转移方程：

$$dp(m,n)=\begin{cases} \max\limits_{0\leq x\leq m}\{dp(x,n-1)+f_n(m-x)\},&n\gt1\\\\ f_1(m),&n=1 \end{cases}$$

根据动态规划的备忘录性质，均利用二维数组对结果进行存储，进而得到伪码.

• 输入：$m,n,f[1..n,1..m]$ 分别表示持有金额，项目数，第$i$ 个项目投入$j$ 元的收益
• 输出：最大收益

$$\begin{aligned} &\text{Algorithm: }\;\text{Investment}(m,n,f)\\\\ 1.&\;\mathbf{repeat}\;dp[j,i]\leftarrow 0\;\mathbf{until}\;\text{dp初始化完毕}\\ 2.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;n\;\mathbf{do}\\ 3.&\;\qquad\mathbf{for}\;j\;=0\;\mathbf{to}\;m\;\mathbf{do}\\ 4.&\;\qquad\qquad\mathbf{for}\;k\;=0\;\mathbf{to}\;j\;\mathbf{do}\\ 5.&\;\qquad\qquad\qquad dp[j,i]\leftarrow \text{max}(dp[j,i],dp[k,i-1]+f[i,j-k])\\ 6.&\;\mathbf{return}\;dp[m,n] \end{aligned}$$

显然，对于最内层循环，需要执行$j+1$ 次加法，$j$ 次比较。次内层指示出$j:0\to m$，最外层指示出执行$n$ 次。
从而该算法的时间复杂度$\begin{aligned}T(m,n)=\sum_{i=1}^n\sum_{j=0}^m[(j+1)+j]=O(nm^2)\end{aligned}$
从备忘录可知，空间复杂度为$O(nm)$.

解的追溯

除了计算最大收益之外，还可以在算法中建立一个标记矩阵从而得以追溯使得最大收益成立的具体决策。

设置标记$mark[i,j]$ 用于表示对前$j$ 个项目投入$i$ 元的最优决策时，对前$j-1$ 个项目投入的金额。
因此得到递推关系：

$$\begin{aligned} x_n&=m-mark[m,n]\\ x_{n-1}&=(m-x_n)-mark[x_n,n-1]\\ x_{n-2}&=(m-x_n-x_{n-1})-mark[x_{n-1},n-2]\\ \cdots&=\cdots\\ x_1&=(m-\sum_{k=2}^nx_k)-mark[x_2,1] \end{aligned}$$

实例展示与代码

假设给定如下数据，其中手持金额$m=5$，可选投资项目$n=4$，对项目$i$ 投入$x$ 获得的收益$f_i(x)$ 如下表所示。

$x$	$f_1[x]$	$f_2[x]$	$f_3[x]$	$f_4[x]$
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

下面先给出对该问题的 C++ 编程实现：

#define M 20

int f[5][6] = {{0,0,0,0,0,0},
			   {0,11,12,13,14,15},
			   {0,0,5,10,15,20},
			   {0,2,10,30,32,40},
			   {0,20,21,22,23,24}};

int mark[M][M];

int Inverstment(int m, int n){
	int dp[M][M];
	memset(dp,0,sizeof(dp));
	memset(mark,0,sizeof(mark));
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= j; k++){
				//dp[j][i] = max(dp[j][i],dp[k][i-1]+f[i][j-k]);
				if(dp[k][i-1]+f[i][j-k] > dp[j][i]){
					dp[j][i] = dp[k][i-1]+f[i][j-k];
					mark[j][i] = k; //标记 
					//持有 j 元 投入前 i 个项目时，对前 i-1 个项目投入 k 元
				}
			}
		}
	}
	return dp[m][n];
}

void get_solve(int m, int n){
	// 通过 mark数组 反推解
	vector<int> X = vector<int>(n);
	for(int i = n-1; i >= 0; i--){
		X[i] = m-mark[m][i+1];
		m = mark[m][i+1];
	}
	for(int i = 0; i < X.size(); i++){
		cout << "x" << i+1 << "=" << X[i] << endl;
	}
}

根据算法构建备忘录表格：

$x$	$dp[x][1],mark[x][1]$	$dp[x][2],mark[x][2]$	$dp[x][3],mark[x][3]$	$dp[x][4],mark[x][4]$
0	0, 0	0, 0	0, 0	0, 0
1	11, 0	11, 1	11, 1	20, 0
2	12, 0	12, 2	13, 1	31, 1
3	13, 0	16, 1	30, 0	33, 2
4	14, 0	21, 1	41, 1	50, 3
5	15, 0	26, 1	43, 1	61, 4

从而，$dp[5][4]=61$ 即为所求的最大收益。

根据标记的回溯原则，可以分别得到：$(x_1,x_2,x_3,x_4)=(1,0,3,1)$

代码的运行结果也正是如此：

max:61
    
x1=1
x2=0
x3=3
x4=1

变位压缩| Variable Identification Compression

本问题取自 中国大学MOOC 由北京大学的屈婉玲教授讲解的 动态规划 一节里的经典例题。

能力有限，我只找到这种特殊的图像变位压缩方法最早出现在 2001年版《计算机算法设计与分析》（王晓东 箸）一书中， 该书涉及的算法示例颇多，并且MOOC上的例题基本出自此书。后来才得知，屈婉玲老师于2011年出版的《算法设计与分析》正是在该书的基础上改进了很多饱受诟病的语言描述和字符混乱问题，并且结合《算法导论》增加了问题的正确性证明，加深了数学语言的表示。

不过对于本节的数字图像变位压缩问题，还是溯源无果，因此此处的英文名取自同样引用王晓东一书的期刊文献：

[1]丁爱芬, 周华君, 石宜金. 一种基于变位与反转变换的动态规划压缩算法[J]. 西南师范大学学报：自然科学版, 2020, 45(1):5.

技术描述

给定一幅灰度图，其像素个数为$n$，由这$n$ 个像素的灰度值构成一个序列$\{p_1,p_2,...,p_n\}$.
其中，$\forall p_i,\;p_i\in[0:1:255]$ 表明该图像的灰度值可由8位二进制数组成. 进而该灰度图的像素序列可由$8n\;bit$ 的数据流（我们同样用序列$\{p_1,p_2,...,p_n\}$ 表示）构成。

下给出一种变位的压缩思想对该序列实现无损压缩。其主要思想是：

1. 将序列分为$m$ 段，分别用$S_1,S_2,...,S_m$ 表示，使得$\bigcup\limits_{i=1}^m S_i=\{p_1,p_2,...,p_n\}$；
2. 段$S_i$ 中的第$k$ 个像素点用$p_k^{(i)}$ 表示，记$S_i$ 中像素点的总个数为$l_i$ ；
3. 对$\forall p_k^{(i)}\in S_i$ 的灰度值不再使用 8 位表示，而采用$h_i\leq 8$ 位进行表示.

则$h_i$ 的使用实现了像素灰度值位数的变换，也就实现了图像的压缩。下面是$h_i$ 的具体计算：

选出$S_i$ 内的最大像素值$p_k^{(i)}$，其所占的位数，即为$h_i$. 有：

$$h_i=\left \lceil\log_2\left(\max\limits_{p_k^{(i)} \in S_i}{p_k^{(i)}}+1\right)\right\rceil\leq 8$$

那么 对于$S_i$ 内的所有像素点来说，它们的灰度值都小于或等于该像素的灰度值，对应的二进制位数也自然不会高于$h_i$. 从而可以对每一段实现数据压缩，进而对整体序列实现压缩。

为了让计算机知道每一个分段下具体有几个像素，灰度值用几位表示，本算法规定对每一段$S_i$ 的 段头 都先用 11 位的标志位来记录本段的存储情况.
标志位包括像素个数$l_i$（最高256，用 9 位表示）和灰度值位数$h_i$（最高 8 位，用 3 位表示）

也就是说，任意一段$S_i$ 的长度应该是：$11+h_i\times l_i$.

从而，最优的压缩就是寻找到这样一种分段策略$T=\{S_1,S_2,\cdots,S_m\}$ 使得总的存储位数最小。即：

$$\max_{T}\sum_{i=1}^m(11+h_il_i)$$

状态转移方程

考虑从$p_1$ 开始到某个像素点$p_i$ 这一子序列的最小存储位数划分问题。我们将末尾像素的下标$i$ 作为状态，其最小存储位数就记为$dp(i)$.

从后往前思考，假设已知$dp(1)\cdots dp(i-1)$ 的值和分割结果，那么该问题可能的划分有：

1. 末尾的单像素$\{p_{i}\}$ 自成一个划分$S_m$ 再与通过$dp(i-1)$ 划分好的序列$T'=\{S_1,S_2,...,S_{m-1}\}$ 共同构成一个可能的划分$T=\{S_1,S_2,\cdots,S_m\}$.
2. 末尾的两个像素$\{p_{i-1},p_i\}$ 自成一个划分$S_m$ 再与通过$dp(i-2)$ 划分好的序列$T'=\{S_1,S_2,...,S_{m-1}\}$ 共同构成一个可能的划分$T=\{S_1,S_2,\cdots,S_m\}$.
3. 末尾的3个像素$\{p_{i-2},p_{i-1},p_i\}$自成一个划分$S_m$ 再与通过$dp(i-2)$ 划分好的序列$T'=\{S_1,S_2,...,S_{m-1}\}$ 共同构成一个可能的划分$T=\{S_1,S_2,\cdots,S_m\}$.
4. ...
5. 将整个序列$\{p_1,p_2,...,p_i\}$ 直接看成一个划分.
   （如果规定$dp(0)=0$，则可以和以上情况统一起来）

如图所示，对于上述的第$j$ 种情况而言，可以直接计算出在此划分下的存储位数：

$$dp(i-j)+h(i-j+1,i)\times j+11$$

其中，$h(i-j+1,i)$ 表示的是从后往前取$j$ 个像素自成一组时（如果是$S_m$ 的话），其最高灰度值所占的位数$h_m$. 有：

$$\begin{aligned} h_m&=\left \lceil\log_2\left(\max\limits_{p_k^{(m)} \in S_m}{p_k^{(m)}}+1\right)\right\rceil\\ &=\left \lceil\log_2\left(\max\limits_{i-j+1\leq k\leq i}{p_k}+1\right)\right\rceil=h(i-j+1,i) \end{aligned}$$

所以，我们只需搜索所有可能的分割点$j:1\to \min\{i,256\}$ ，从中求出最小的存储位数即$dp(i)$ 。最高取 256 是因为一个分割的最大像素个数已经被规定为 256.

最终得到状态转移方程如下：

$$dp(i)=\begin{cases} \min\limits_{1\leq j\leq i}\{dp(i-j)+h(i-j+1,i)\times j+11\},&n\geq1\\ 0,&n=0 \end{cases}$$

伪码与性能分析

分析转移方程可知，$dp(n)$ 就是我们需要求解的结果。而其依赖于$dp(1..n-1)$. 并且，需要自底向上，从小到大地求解并存储子问题的答案。
因此，我们利用一维数组$dp[0..n]$ 存储动态规划表，构建循环体$i:1\to n$ 设计算法。

为了追溯划分策略，还可以建立一维数组$split[1..n]$ 记录状态为$i$ 时，划分出来的末尾序列的起点下标。

为了避免繁琐的计算，算法对输入的数组$p[1..n]$ 生成对应下标的灰度值位数数组$h[1..n]$，使得$h[i]$ 存储的是对应下标的像素$p_i$ 的灰度值的位数，即$h[i]=\left \lceil\log_2\left(p[i]+1\right)\right\rceil$.

所以，对于转移方程中的$h(i-j+1,i)$ 也不需要重复计算，只需用一个变量$hmax$ 在每次迭代循环时判断是否存在新的最大位数即可。

算法伪码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{Compression}(p,n)\\\\ 1.&\;\text{初始化数组 }dp,\;split\\ 2.&\;dp[0]\leftarrow0\\ 3.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;n\;\mathbf{do}\\ 4.&\;\qquad hmax\leftarrow h[i]\leftarrow\left \lceil\log_2\left(p[i]+1\right)\right\rceil\\ 5.&\;\qquad dp[i]\leftarrow dp[i-1]+hmax\\ 6.&\;\qquad split[i]\leftarrow 1\\ 7.&\;\qquad\mathbf{for}\;j\;=2\;\mathbf{to}\;\min\{i,256\}\;\mathbf{do}\\ 8.&\;\qquad\qquad hmax\leftarrow \max(hmax,h[i-j+1])\\ 9.&\;\qquad\qquad tmp\leftarrow dp[i-j]+j\times hmax\\ 10.&\;\qquad\qquad \mathbf{if}\;tmp\lt dp[i]\;\mathbf{then}\\ 11.&\;\qquad\qquad\qquad dp[i]\leftarrow tmp\\ 12.&\;\qquad\qquad\qquad split[i]\leftarrow j\\ 13.&\;\qquad\qquad dp[i]\leftarrow dp[i]+11\\ 14.&\;\mathbf{return}\;dp,\;split \end{aligned}$$

【注】一些说明：

1. 伪码中的$j$ 是从 2 开始的。这是因为在 4 至 6 行 我们直接对$j=1$ 的情况进行了处理
2. 因为转移方程中存在常数 11，它不影响比较，因此统一将 11 放到一次大循环后添加（第 13 行）
3. 第 4 行的$h[i]$ 总是随着$i$ 的增大不断填充，并且此时$hmax$ 总是状态为$i$ 时最右端的位数。而随着$j$ 的增加，末尾序列从当前最右端$p_i$ 逐步往左延长，所以在 第 8 行$hmax$ 只需与当前划分的最左端$p_{i-j+1}$ 的位数进行对比即可，而不需要再从最右端开始遍历。

由于$j$ 的循环最高$256$ 次，与$n$ 无关，因此即使$n$ 很大$j$ 的循环次数最坏也是$W(n)=256=O(1)$。而$i$ 的循环依赖于$n$ ，所以本算法总体的时间复杂度为$O(n)$.

根据备忘录的大小可知，本算法的空间复杂度应为$O(n)$.

编程实现

#define M 256+1

int dp[M];
int split[M];

int Len(int p){
	// 计算灰度值的二进制位数
	int res = 0;
	while(p){
		res++;
		p = p/2;
	}
	return res;
}

int Compression(int p[], int n){
	memset(dp,0,sizeof(dp));
	memset(split,0,sizeof(split));
	int h[M] = {0};
	int hmax = 0;
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		h[i] = Len(p[i]);
		hmax = h[i];
		dp[i] = dp[i-1]+hmax;
		split[i] = i;
		for(int j = 2; j <= min(i,256); j++){
			hmax = max(hmax,h[i-j+1]);
			int tmp = dp[i-j]+j*hmax;
			if(dp[i] > tmp){
				dp[i] = tmp;
				split[i] = j; 
				//标记以 i 结尾时，末位的j个像素为一组 最优
			}
		}
		dp[i] += 11;
	}
	return dp[n];
}

void Traceback(int n){
	// 追溯解
	int i = 1;
	int right = n;
	int left = right-split[right]+1;
	while(right){
		cout << "group " << i << ": (" << left << ", " << right << ")" << endl;
		right = left-1;
		left = right-split[right]+1;
		i++;
	}
}

输出结果如下：

min bit = 57

group 1: (5, 6)
group 2: (1, 4)

表示将 [1-4] 分为一组，[5-6]分为一组时，可使得存储位数最小，且最小为57位。

数塔问题

HDU

1. 贪心
2. 暴力 O(2^n)
3. DP O(n^2/2)

免费馅饼

#include<iostream>
#include<string.h>
using namespace std;

int maxof3(int a,int b,int c){
    int tmp = max(a,b);
    return max(tmp,c);
}
int dp[100001][12];
int main(void){
    int n;
    int x,y,x_max=0;
    int i,j;
    
    while(cin >> n){
        if(n == 0) return -1;
        memset(dp,0,sizeof(dp));
        for(i = 0; i < n; i++){
            scanf("%d%d",&y,&x);
            dp[x][y]++;
            x_max = max(x_max,x);
        }
        for(i=x_max;i>0;i--)
      {
          for(j=0;j<=10;j++)
          dp[i-1][j]+=maxof3(dp[i][j],dp[i][j+1],dp[i][j-1]);
      }
        cout << dp[0][5] << endl;
    }

    return 0;
}

搬寝室

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int dp[2000][1000];
int main(void){
    int n,k;
    int i,j;
    int a[2000];
    // int dp[9][9];
    while(~scanf("%d%d",&n,&k)){
        memset(a,0,sizeof(a));
        memset(dp,inf,sizeof(dp));
        for(i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        dp[0][0]=dp[1][0]=0;
        dp[2][1] = (a[0]-a[1])*(a[0]-a[1]);
        for(i = 2; i <= n; i++){
            dp[i][0]=0;
            for(j = 1; j <= k; j++){
                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(a[i-1]-a[i-2])*(a[i-1]-a[i-2]));
            }
        }
        cout << dp[n][k] << endl;
    }
    
    return 0;
}

最长上升子序列

小规模

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1000010;
const LL mod = 1000000007;

LL a[maxn];
int dp[maxn];

#define CPC
int main(void){
#ifdef CPC
    char bufin[40012],bufout[40012];
    for(int t = 1; t <= 1; t++){
        sprintf(bufin,"%02d.in", t);
        sprintf(bufout,"%02d.out2",t);
        freopen(bufin,"rb", stdin);
        freopen(bufout, "wb", stdout);
#endif
    LL n, b;
    while(~scanf("%lld%lld",&n,&b))
    {
		a[1] = b; dp[1] = 1;
		for(int i = 2; i <= n; i++){
			a[i] = 1LL*(a[i-1]+1)*(a[i-1]+1)%mod;
			dp[i] = 1; //初始化为 1
			// cout << a[i] << " ";
		}
		int res = 0;
		for(int i = n-1; i >= 1; i--){
			for(int j = i+1; j <= n; j++){
				if(a[j] > a[i]){
					dp[i] = max(dp[i], dp[j]+1);
				}
			}
			res = max(dp[i], res);
		}
		printf("%d\n",res);
    }
#ifdef CPC
    }
#endif
    return 0;
}

大规模

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1000010;
const LL mod = 1000000007;

LL a[maxn];
int dp[maxn];

#define CPC
int main(void){
#ifdef CPC
    char bufin[40012],bufout[40012];
    for(int t = 1; t <= 1; t++){
        sprintf(bufin,"%02d.in", t);
        sprintf(bufout,"%02d.out2",t);
        freopen(bufin,"rb", stdin);
        freopen(bufout, "wb", stdout);
#endif
    LL n, b;
    while(~scanf("%lld%lld",&n,&b))
    {
		a[1] = b; dp[1] = mod;
		for(int i = 2; i <= n; i++){
			a[i] = 1LL*(a[i-1]+1)*(a[i-1]+1)%mod;
			dp[i] = mod; //初始化为最大可能的值
			// cout << a[i] << " ";
		}

		//贪心 + 二分查找 方法
		int k = 1;
		for(int i = 1; i <= n; i++){
			if(dp[k] < a[i]) dp[++k] = a[i];
			else{
				*lower_bound(dp+1, dp+k, a[i]) = a[i]; //把 dp[] 中第一个比a[i]小的位置的值替换成a[i]
			}
		}
		printf("%d\n",k);
    }
#ifdef CPC
    }
#endif
    return 0;
}

待更参考：https://zhuanlan.zhihu.com/p/121032448

参考

1. 《算法导论(原书第三版)》
2. 算法设计与分析|中国大学MOOC
3. HDForum-动态规划|by杭电刘春英
4. 图像压缩问题|博客园