算法分析复习2（动态规划）

算法分析复习1由于懒惰，没有及时整理。今天直接整理2（其实本来该复习系统和离散的,但是我太想学算法了，没忍住）
第三章 动态规划（dp）
算法分析课本上有七个问题

最重要（简单）的三个：
最大子段和
最长公共子序列
0/1背包问题
剩下的几个：
矩阵连乘问题
凸多边形最优三角剖分
图像压缩
流水作业调度
最优二叉树

按顺序来

最大子段和

【题目描述】
小 Q 是一个宝石爱好者。这一天，小 Q 来到了宝石古董店，店家觉得小 Q 是个宝石行家，于是决定和小 Q 玩一个游戏。
游戏规则：一共有n块宝石，每块宝石在小 Q 心中都有其对应的价值。注意，由于某些宝石质量过于差劲，因此存在只有店家倒贴钱，小 Q 才愿意带走的宝石，即价值可以为负数。​小 Q 可以免费带走一个连续区间中的宝石，比如区间[1, 3]或区间[2, 4]中的宝石。请问小 Q 能带走的最大价值是多少？
【举例】
[-2, 11, -4, 13, -5, -2]

最大价值？

区间[2, 4]，20
【解答】
暴力法就不演示了，反正一个O(n²)一个O(n³)

分治

这题居然还可以分治，来，我们看看分治做法

int MaxSubSum(int *a,int left,int right) {
int sum=0;
if(left==right) {
sum=a[left]>0?a[left]:0; //当子段被划分为一个个点，对于每个点而言，最大子段为取或不取，取为本身值，不取为0
}
else {
int mid=(left+right)/2;
int leftsum=MaxSubSum(a,left,mid);//起始终止点都在mid左边的子段和
int rightsum=MaxSubSum(a,mid+1,right);//起始终止点都在右边的子段和

int s1=0,lefts=0;//起点左边，终止右边的子段和
for(int i=mid;i>=left;i--) {
lefts+=a[i];
if(lefts>s1) s1=lefts;//起始点在mid左边的sum
}
int s2=0,rights=0;
for(int i=mid+1;i<rights;i++) {
rights+=a[i];
if(rights>s2) s2=rights;//终止点在mid右边的sum
}
sum=s1+s2;//起始点在mid左右的子段和
if(sum<leftsum) sum=leftsum;
if(sum<rightsum) sum=rightsum;
return sum;//选出这三个里面最大的
}
}

不错，很分治,复杂度O(nlogn)

dp

dp代码是要求记住的，动态规划方程(请定义清楚)
sum[i]=sum[i-1]+a[i] (sum[i-1]>0)
sum[i]=a[i] (sum[i-1]<0)

代码实现：

int MaxSum(int n,int* a) {
int b=a[0],sum=0;
for(int i=1;i<n;i++) {
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;//该dp方程只能保证以a[i]为结尾的最大子串和，不能保证全局，所以需要sum来记录最大值
}
return sum;
}

复杂度O(n)

最小路径和

【题目描述】
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

数据范围：
1 <= m, n <= 200
0 <= grid[i][j]<= 100

将当前在某格定义为当前状态
dp方程如下：
设每一状态的权值表示为f(i,j) 每个格子的权值表示为a[i][j]
f(i,j)=max{f(i-1,j)+a[i][j]，f(i,j-1)+a[i][j]}

代码实现：
（题目来自leetcode）

int minPathSum(vector<vector<int> >& grid) {
if(grid.size()==0||grid[0].size==0) {//检验路劲数组非空
return 0;
}
int rows=grid.size(),columns=grid[0].size();
auto dp=vector<vector<int> > (rows,vector<int> (colcumns));
dp[0][0]=grid[0][0];
for(int i=1;i<rows;i++) {//初始化状态表边界
dp[i][0]=dp[i-1][0]+grid[i][0];//dp的坐标是从(1,1)开始的
}
for(int j=1;j<columns;j++) {//初始化状态表边界
dp[0][j]=dp[0][j-1]+grid[0][j];//dp的坐标是从(1,1)开始的
}
for(int i=1;i<rows;i++) {
for(int j=1;j<columns;j++) {
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[rows-1][columns-1];
}

乘积最大子数组

很像最大子段和，不同的看下面状态方程就好了
if(a[i]>0)
{maxn[i]=max(maxn[i-1]*a[i],a[i]);
minn[i]=min(minn[i-1]*a[i],a[i]);}
else {
maxn=max(minn[i-1]*a[i],a[i]);
minn=min(maxn[i-1]*a[i],a[i]);
}
代码我拿上面的最大子段和改一改：

int MaxSum(int n,int* a) {
int maxn[n],minn[n];
int max=a[0];
for(int i=1;i<n;i++) {
if(a[i]>0) {
maxn[i]=max(maxn[i-1]*a[i],a[i]);
minn[i]=min(minn[i-1]*a[i],a[i]);
}
else {
maxn[i]=max(minn[i-1]*a[i],a[i]);
minn[i]=min(maxn[i-1]*a[i],a[i]);
}
if(maxn[i]>max) max=maxn[i];//该dp方程只能保证以a[i]为结尾的最大子串和，不能保证全局，所以需要sum来记录最大值
}
return max;
}

最长公共子序列

dp方程
设两字符串分别为x,y，其中第i个元素为xi,yi
D(i,j)为xi和yj为结尾时，最大公共子串的长度
if(xi=yi)
D(i,j)=D(i-1,j-1)+1;
else
D[i][j]=max(D(i-1,j),D[i][j-1])
经典的查表方法，下面放代码：

int maxsubstr(string a,string b){//返回值为最大子串长度即int型数据
int strlen1=a.length(),strlen2=b.length();
//int n=max(strlen1,stelen2);
//这么写可以，但是需要明白状态表D[i][j]的含义，即D[i][j]表示在比较到a的第i个字符，b的第j个字符时，最长公共子序列的长度
int i=0,j=0;
int D[strlen1+1][strlen2+1];
setmem(D,0,sizeof(D));
for(int i=1;i<strlen1;i++) {//定义了状态，那遍历的就是状态了，不能直接从模拟的角度遍历字符串
for(int j=1;j<strlen2;j++) {
if(a.at(i-1)==b.at(j-1)) D[i][j]=D[i-1][j-1]+1;
else D[i][j]=max(D[i-1][j],D[i][j-1])；
}
}
return D[strlen1][strlen2];
}

01背包（dp方法）

定义状态f(i,j)为，以a[i]为结尾的物品序列，背包剩余重量为j时对应的价值。
状态转移方程：
if(j>W[i]) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+a[i]) //如果剩余容量大于当前物品可以选择装与不装
else f[i][j]=f[i-1][j] //如果剩余容量小于当前物品，只能选择装
代码：

void bag(int* a,int* w,int n,int size) {
//传入物品价值，物品重量，物品数量，背包大小
int f[n][size+1];//第一个物品编号为0,背包状态为size+1，即加入0状态
//初始化dp数组
for(int i=0;i<n;i++) {
/*以第i个物品，在背包容量为0时，很好理解，
如果背包什么都装不下了，不管序列有多长，总价值都是0*/
f[i][0]=0;
}
for(int i=0;i<size;i++) {
if(i>w[0]) f[0][i]=a[0];
else f[0][i]=0;
}
for(int i=1;i<n;i++) {
for(int j=0;i<=size;j++) {
if(j>w[i]) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+a[i]);
else f[i][j]=f[i-1][j];
}
}
return f[n-1][m];
}

我菜，整点简单的(爬楼梯dp方法)

int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
// return climbStairs(n-1)+climbStairs(n-2);
int D[n+1];
D[1]=1;
D[2]=2;
for(int i=3;i<=n;i++) D[i]=D[i-1]+D[i-2];
return D[n];
}

最后

以上就是激昂冬瓜为你收集整理的算法分析复习2（动态规划）的全部内容，希望文章能够帮你解决算法分析复习2（动态规划）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。