现在做个企业网站一般多少钱_xd网页设计教程_推广商_网店运营公司

一、动态规划

1. 概念

1.1 动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。深搜（dfs）就是一种动态规划，优化方式为记忆化搜索（用空间换时间），再优化就变成了动态规划（递归优化到递推）。

1.2 最优子结构

如果一个问题的最优解可以从其子问题的最优解构建出来，那么我们说这个问题具有最优子结构特性最优子结构意味看可以通过组合子问题的最优解来得到原问题的最优解。

1.3 子问题重叠

如果有大量的重叠子问题，可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。这种方法叫做记忆化搜索。

1.4 无后效性

动态规划具有无后效性，深搜和记忆化搜索有时没有。

• 未来与过去无关。
• 已经求解的子问题，答案不会再受到后续决策的影响。
• 一旦得到了小问题的解，那么如何得到的这问题的解跟求解大问题的无关。

2. 基本思路

1. 将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（状态定义）。
2. 寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（状态转移）。
3. 按顺序求解每一个阶段的问题。

3. 模板

3.1 最大子段和

dp[i]：以 $i$ 为结尾的最大子段和

dp[i]=max(dp[i-1],0)+a[i];//选择和前面的序列进行拼接或单独成一个序列

3.2 最大子矩阵和

for(int i=1;i<=n;i++)for(int j=1,a;j<=m;j++)cin>>a,pfx[i][j]=pfx[i][j-1]+a;//求出每行的前缀和
for(int l=1;l<=m;l++)//枚举列的左端点for(int r=l;r<=m;r++)//枚举列的右端点for(int i=1;i<=n;i++){//一维最大子段和模板dp[i]=max(dp[i-1],0)+pfx[i][r]-pfx[i][l-1];ans=max(ans,dp[i]);}

3.3 最长上升子序列

$O(n^2)$ 解法：
dp[i]：以 $i$ 为结尾的最长上升子序列长度

for(int i=1;i<=n;i++)for(int j=i-1;j>=0;j--)//接在a[0]后面表示自己单独成为一个序列if(a[i]>a[j])//判断是否上升dp[i]=max(dp[i],dp[j]+1);//接在后面，序列长度+1

二、例题

1. 单词的划分

1.1 审题

描述
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分都必须是字典中的一个单词。 出于减少分析量的目的，我们希望划分出的单词数越少越好。 你就是来完成这一划分工作的。给出字符串和字典，输出最少的划分单词数。

输入

realityour
5
real
reality
it
your
our

输出

2

1.2 分析

这道题目是一个动态规划题。具体思路：

• dp[i] 存储 s[0]~s[i-1] 这个子字符串最少可以分成多少个单词；
• 遍历每一个哨兵位置，看看 s[0]~s[i-1] 这个子字符串的末尾（因为前面已经被单词分割过了）是不是有字典中的单词，并按照这种分割方法（前面的分割+匹配的单词）进行存储

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXL=1e3+8;
const int INF=0x3f3f3f3f;
int n,m,dp[MAXL];//dp[i]:s[0]~s[i-1]最少能划分成多少个单词
set<string>dic;//单词表
string s,t;
int main(){cin>>s>>n;m=s.size();for(int i=1;i<=n;i++)cin>>t,dic.insert(t);memset(dp,INF,sizeof(dp));dp[0]=0;for(int i=1;i<=m;i++)//遍历哨兵位置for(auto t:dic)//遍历字典里的所有单词if(i>=t.size()&&s.substr(i-t.size(),t.size())==t)//如果当前遍历到的单词长度可以包含在a[1]~a[i]这个长度中//并且s的后几位就是当前遍历到的单词dp[i]=min(dp[i],dp[i-t.size()]+1);//更新为上一次划分地方的划分数量+1cout<<dp[m];return 0;
}

2. 数列划分

2.1 审题

给出 $n$ 项的数列，要求将数列划分成若干段，且每一段之和都不超过 $s$。 求一共有多少种满足要求的划分方法。方法数很大，只要求输出除以 $10^9$ 的余数。

2.2 分析

先遍历所有的最后一个序列的左端点和右端点，让以 j 结尾的划分后面再添上 [j+1,i] 这样的一段序列。

2.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
const int MOD=1e9;
int n,s,pfx[MAXN],dp[MAXN];
int main(){cin>>n>>s;for(int i=1,a;i<=n;i++)cin>>a,pfx[i]=pfx[i-1]+a;dp[0]=1;//最后一段的划分是[j+1,i]for(int i=1;i<=n;i++)//先遍历前面的数列进行划分for(int j=i-1;j>=0&&pfx[i]-pfx[j]<=s;j--)//j:倒数第二段的终点 且这一段的和满足题目条件//从短的一段开始遍历，直到左端点j走到0//pfx[i]-pfx[j]<=s写在for循环的条件里//是因为如果[i-1,i]这样一段都已经超过了s//[i-2,i]、[i-3,i]必然都会超过s//因为所有元素为正，所以可以直接跳出dp[i]=(dp[i]+dp[j])%MOD;//以j结尾的划分后面再添上一段[j+1,i]序列cout<<dp[n];return 0;
}

3. 老鼠速度

3.1 审题

给出 $n$ 只老鼠的数据，分别是它们的体重和速度。为了证明越重的老鼠速度越慢，我们要找出一组数据，由若干个老鼠组成，保证老鼠的体重依次增加而速度依次减小。问最多能找出多少只老鼠？

3.2 分析

我们可以使用最长下降子序列的方法实现。具体如下：

• 将老鼠的体重按升序排序
• 挑选出速度的最长下降子序列

3.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
int n,dp[MAXN];
struct Mouse{int w,v;bool operator<(const Mouse&rhs)const{if(w!=rhs.w)return w<rhs.w;return v<rhs.v;}
}a[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].v;sort(a+1,a+n+1);a[0]={0,10008};//第0个老鼠设置成极小体重和极快速度for(int i=1;i<=n;i++)for(int j=i-1;j>=0;j--)if(a[i].v<a[j].v)//最长下降子序列dp[i]=max(dp[i],dp[j]+1);int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[i]);cout<<ans;return 0;
}

4. 字符串改造

4.1 审题

小明有一个字符串，由小写英文字母组成。
小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符（$a<b<\cdots <z$）。
例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要求。或者小明删除第二字母，变成 hppy，也满足要求。小明还有其他方法使得结果满足要求。再如，对于字符串 autumn，可以删除三个字母变成 amn，或者删除四个字母变成 at。其他满足要求的方案还有很多。
小明想知道，对于一个字符串，至少要删除多少个字母能满足要求。

4.2 分析

dp[i]：字符 $i$ 结尾的最长递增子序列的长度。
接下来：

• 遍历所有可能将 ch 接在后面的字符（a ~ ch）
• 更新以 ch 为结尾的最长递增子序列的长度
• 取所有长度中的最大值
• 输出输入的字符串长度 $-$ 保留长度的最大值

4.3 参考答案

#include<bits/stdc++.h>
using namespace std;
int dp[208];
string s;
int main(){cin>>s;for(char ch:s)for(int i=ch;i>='a';i--)//遍历所有可能将ch接在后面的字符dp[ch]=max(dp[ch],dp[i]+1);int ans=0;for(int i='a';i<='z';i++)ans=max(ans,dp[i]);cout<<s.size()-ans;return 0;
}