刷题：
form 《tzcxsjjs》
-p64
-p66
说明-动规
动规也被称为迭代。听说dp很难理解，又很重要。动态规划都有哪些实际应用呢？
生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！
动规的特点
使用dp可找到最优解。它是从小问题着手，逐步解决大问题。
dp可以很好地解决背包问题，当且仅当约束条件（背包容量）/子问题是离散时，dp才管用。
每种动态规划解决方案都涉及网格，格中的值便是需要你优化的值。
每次迭代时，你都存储当前的最大价值。
没有放之四海皆准的计算动态规划解决方案的公式。
01背包
问题描述
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
可以用穷竭搜索法，但是它的效率不比动态规划。学习多种算法，尽可能地做到每种问题的最优解。
限制条件
1<=n<=100
1<=wi,vi<=100
1<=W<=10000
解题
（1）
/*dfs*/
int dp[MAX_N+1][MAX_W+1];//记忆化数组
int rec(int i,int j){
if(dp[i][j]>=0){
//已经计算过的话直接使用之前的结果
return dp[i][j]；
}
int res;
if(i==n){
res=0;
}else if(j<w[i]){
res=rec(i+1,j);
}else{
res = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
}
return dp[i][j]=res;
}
void solve( ){
memset(dp,-1,sizeof(dp));
printf("%d\n",rec(0,w));
}
(2)
/*dp-逆向进行的迭代。*/
int dp[MAX_N+1][MAX_W+1]
void solve(){
for(int i=n-1;i>=0;i--){
for(int j=0;j<=w;j++){
if(j<w[i]){
dp[i][j]=dp[i+1][j];
}else{
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}
}
printf("%d\n",dp[0][w]);
}
/*dp算法很巧妙，j初值为0也好，还是为W，最大值都在最后一个格子里。*/
(3)
void solve(){
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++){
if(j<w[i]){
dp[i+1][j]=dp[i][j];
}else{
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
cout<<dp[n][W]<<endl;
}
/*
dp数组用来存储数据，并且也充当了book。
可看出这是一个n(i)行w(j)列的矩阵，迭代到最后一格时，得到最大值。
其中，当j（可用空间）不小于w（物品实际空间时），才能更新最大值。
当j<w[i]，最大值不变，向(i+1,j)迭代，直到j不小于w[i]。
*/
（4）
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<=W;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+w[i]<=W]){
dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
}
}
cout<<dp[n][w]<<endl;
}
（5）
/*01背包之dp最终版
和下文的完全背包相呼应*/
for(int i=0;i<n;i++){
for(int j=W;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[W];
最长公共子序列问题
核心伪代码如下。
if word_a[i] == word_b[j]://step1:如果两字母相同
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = max(cell[i-1][j], cell[i][j-1]) //step2:如果不同，就选邻居中较大的那一个。
【解题】
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i]==t[j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
}
}
}
cout<<dp[n][m]<<endl;
}
完全背包问题
[描述]
完全背包问题是指每种物品都有无限件，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。
（1）
void solve()
{
for(int i=0;i<n;i++){
for(int j=0;j<=W;j++){
for(k=0;k*w[i]<=j;k++){
dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-k*w[i]]+k*v[i]);
}
}
}
cout<<dp[n][W]<<endl;
}
（2）
void solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++){
if(j<w[i]){
dp[i+1][j]=dp[i][j];
}else{
dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
}
}
cout<<dp[n][W]<<endl;
}
（3）
/*完全背包之其最终版*/
void solve()
{
for(int i=0;i<n;i++){
for(int j=w[i];j<=W;j++){
dp[j]=max(dp[j],dp[j-w[i]+v[i])
}
}
cout<<dp[W];
}
小张累了，这完全背包的终结版和01背包的终结版，除了循环方向，就没什么不同了呢。
简化代码什么的，真的有够厉害的。以前做什么代码题，都是能运行出来就万事大吉了。（哈哈哈= = ）
追求完美什么的，真的还有够累人的。（不追求又不行）
可能我以后写dfs，或dp代码，会很像啊哈磊和隆部的代码。
毕竟思路是从他们那学来的。
我学习编程可从来都不靠背的哦。（靠记忆学习的坏习惯也是接触了编程才改过来）
虽然一直拥有着比较好的记忆力，但对此我一直不屑，现在哪怕学语言都不想靠记性（这也是为什么我的语言那么菜吗）OK不啰嗦。
大三要开算法课来着，为了能让我不像大一荒废C语言课（一节没听）一样，我每个算法都没有说学得很透彻，原理都是一知半解的程度。时间不多，而且学太透彻大三上课又没事做。慢慢来，五月还要倒回去学数据结构（大二荒废的结果）。我总是这样，都不按部就班的。
希望经过三年交货时，自己能有良好的数学和专业基础，很强的编程实力，会两门外语以及网页制作。
目标渐渐清晰，不迷茫了。
01背包之二
与上一个01背包不同的是其限制条件：
1<=n<=100
1<=wi<=10^7
1<=vi<=100
1<=W<=10^9
【解题思路】
此前解决此问题的方法的复杂度为O(nW)，书上提供了更改DP对象的方法，复杂度化为了O(nV)，于是就能在时间限制内求出来了。
【解题】
int dp[MAX_N+1][MAX_N*MAX_V+1];
void solve(){
fill(dp[0],dp[0]+MAX_N*MAX_V+1,INF);
dp[0][0]=0;
for(int i=0;i<n;i++){
for(int j=0;j<MAX_N*MAX_V;j++){
if(j<v[i]){
dp[i+1][j]=dp[i][j];
}else{
dp[i+1][j]=dp[i][j];
}else{
dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
}
int res=0;
for(int i=0;i<=MAX_N*MAX_V;i++)
if(dp[n][i]<=W)
res=i;
printf("%d\n",res);
}
最长上升子序列问题
问题描述
一个数的序列 bi，当 b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里 1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是 4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入数据
输入的第一行是序列的长度 N (1 <= N <= 1000)。第二行给出序列中的 N 个整数，这些整数的取值范围都在 0 到 10000。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
g老师的解题思路：
假定 MaxLen (k)表示以ak 做为“终点”的最长上升子序列的长度，那么：
MaxLen (1) = 1
MaxLen (k) = Max { MaxLen (i)：1<i < k 且 ai < ak且 k≠1 } + 1
这个状态转移方程的意思就是，MaxLen(k)的值，就是在 ak 左边，“终点”数值小于 ak，
且长度最大的那个上升子序列的长度再加 1。因为 ak 左边任何“终点”小于 ak 的子序列，
加上 ak 后就能形成一个更长的上升子序列。
实际实现的时候，可以不必编写递归函数，因为从 MaxLen(1)就能推算出 MaxLen(2)，
有了 MaxLen(1)和 MaxLen(2)就能推算出 MaxLen(3)……
来看看g老师友好得代码（tzcxsj的代码真心比这个要难懂一点，先从简单的来）
#include <stdio.h>
#include <memory.h>
#define MAX_N 1000
int b[MAX_N + 10];
int aMaxLen[MAX_N + 10];
int main()
{
int N;
scanf("%d", & N);
for( int i = 1;i <= N;i ++ )
scanf("%d", & b[i]);
aMaxLen[1] = 1;
for( i = 2; i <= N; i ++ ) { //每次求以第 i 个数为终点的最长上升子序列的长度
int nTmp = 0; //记录满足条件的，第 i 个数左边的上升子序列的最大长度
for( int j = 1; j < i; j ++ ) { //察看以第 j 个数为终点的最长上升子序列
if( b[i] > b[j] ) {
if( nTmp < aMaxLen[j] )
nTmp = aMaxLen[j];
}
}
aMaxLen[i] = nTmp + 1;
}
int nMax = -1;
for( i = 1;i <= N;i ++ )
if( nMax < aMaxLen[i])
nMax = aMaxLen[i];
printf("%d\n", nMax);
return 0;
}
（2）
{
int res=0;
for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
res=max(dp[i],res);
}
cout<<res<<endl;
}
画了网格才明白。
dp里储存着每个数字被大的次数，被大次数最多的就是它的最长子序列长度。
https://blog.csdn.net/lyy289065406/article/details/78702485
（3）
从O(n^2)简化到O(nlogn)的算法来啦！（用到了STL的lower_bound）
lower_bound( begin,end,num)：
从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
也是一段神奇的代码。一眼看不出它到底在干个啥。
int dp[MAX_N];
void solve(){
fill(dp,dp+n,INF);
for(int i=0;i<n;i++){
*lower_bound(dp,dp+n,a[i])=a[i];//地址再加指针就其本身啦
}
printf("%d",(dp,dp+n,INF)-dp);//因为返回的是地址所以要-dp
}
有关计数问题的dp
题目描述：
有n个无区别的物品，将它们划分为不超过m组，求出划分方法数模M的余数。
限制条件：
1≤m≤n≤1000
2≤M≤10000
[解题]：
int dp[MAX_M][MAX_N]
void solve(){
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
if(j-i>=0){
dp[i][j]=(dp[i-1][j]+dp[i][j-i])%M;
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[m][n]<<endl;
}
网友评论