每日算法-两个数组的dp、哈夫曼编码、子序列dp问题+哈希表
计算字符串的编辑距离
题目：
分析：
这道题是一个两个数组的dp问题，依旧是动态规划五步走！
1.状态表示
根据经验就是选取s的一段区间，选取t的一段区间考虑。
dp[i][j]：s的[0,i]和t的[0,j]的最小编辑次数。
2.状态转移方程
根据经验就是根据两个字符串最后一个位置的情况来分类讨论。
当s[i]==s[j]时，s的[0,i]和t的[0,j]的最小编辑次数就是s的[0,i-1]和t的[0,j-1]的最小编辑次数，也就是dp[i-1][j-1]。
当s[i]!=s[j]时，稍微复杂点，有三种情况。
1.删除s[i]
这种情况下dp[i][j]等于dp[i-1][j]+1。
2.在s[i]后插入t[j]字符
这种情况下dp[i][j]=dp[i][j-1]+1
3.把s[i]替换成t[j]
这种情况下dp[i][j]=dp[i-1][j-1]+1
当s[i]!=t[j]时dp[i][[j]是这三种情况的最小值。
3.初始化
因为要用到前一行前一列的dp值，所以给dp表多加一行多加一列方便初始化，第0行代表s字符串为空，所以变成t需要t区间长度次操作，第0列代表t字符串为空，变成s需要s区间长度次操作。
因为多加一行多加一列，填表时要注意下标的映射关系。
4.填表顺序
从上到下从左到右
5.返回值
返回dp[m][n]（dp表多加一行多加一列）
代码：
#include<string> #include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { string s,t; cin>>s>>t; int m=s.size(); int n=t.size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); //初始化 for(int i=1;i<=n;i++) dp[0][i]=i; for(int j=1;j<=m;j++) dp[j][0]=j; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(s[i-1]==t[j-1]) { dp[i][j]=dp[i-1][j-1]; } else { //三种情况最小值 dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1; } } } cout<<dp[m][n]<<endl; return 0; }哈夫曼编码
哈夫曼编码介绍：
哈夫曼编码就是一种压缩存储的方式。
假设我们要保存一个字符串，这个字符串是一篇很长的文字，直接存非常占空间，可以用二进制的方式存。
如何用二进制的方式存呢？
错误编码示范：
给每个字符串中的每个字符进行编码。
可是这样编码在解码的时候会出现的第一个问题是：比如001我们是该解码成一个c还是a和b呢。
第二问题是：c字符占了3个二进制位，我们想要尽可能的压缩，所以这种方法不一定是最优的。
哈夫曼编码完美的解决了这两个问题。
哈夫曼编码：
哈夫曼编码的三步：
1.统计每个字符的频次
比如在上面的字符串中a:1 b:2 c:3 d:2
2.根据频次构建最优二叉树
把四个字符的频次当作二叉树的节点，每次挑选两个节点权值最小的去构建一棵新的树（这里的权值就是字符的频次），重复这个过程，最后构建出一棵最优二叉树。
3.根据最优二叉树编码
左分支编0、右分支编1或左分支编1、右分支编0都可以。
哈夫曼编码题目考察点：
有些题目会问最终每个字符的编码值是多少，原始字符串编码之后的二进制序列长度是多少。
题目：
分析：
这道题考察的就是求哈夫曼编码后二进制序列的长度。
最优二叉树：
最短长度的计算有两种方法。
1.只盯着叶子节点，权值乘上走到根节点的步数，权值为1的节点，1乘2（走两步到根节点），权值为2的节点，2乘2，权值为3的节点3乘1，加在一起就是0。
这种方法比较麻烦，因为要知道叶子节点到根节点的步数。
2.一边构造最优二叉树一边统计最短长度，每次取两个权值最小的节点的同时把这个两个权值加起来。
比如上面的例子，先取1，2，再取3，3，构建完成，和就是9。
因为我们需要频繁的取出最小权值的节点，所以用小根堆来存这些节点（默认是大根堆，要传入比较器（greater<int>类型））。
代码：
#include <iostream> #include<queue> using namespace std; int main() { int n; cin>>n; //用小根堆存节点 priority_queue<long long,vector<long long>,greater<long long>> pq; while(n--) { int a; cin>>a; pq.push(a); } //构建最优树 //同时计算二进制序列长度 long long ret=0; while(pq.size()>1) { long long a1=pq.top(); pq.pop(); long long a2=pq.top(); pq.pop(); pq.push(a1+a2); ret+=a1; ret+=a2; } cout<<ret<<endl; }abb
题目：
分析：
这道题求结果的时候要从前往后推导，所以用线性dp来解。
这道题的解法是动态规划+哈希表。
1.状态表示
子序列问题的状态表示根据经验定义为：以i位置为结尾的子序列......
dp[i]:以i位置为结尾的子序列有多少个abb型的子序列。
2.状态转移方程
假设i位置的字符是x，那么要知道dp[i]的值只需要知道[0,i-1]区间内有多少个_x子序列即可。
引入一个f[26]的哈希表。
所以dp[i]=f[x-'a']，要更新dp[i]只需要更新f[x-'a']即可。
f[x-'a']可以分为两种情况，第一种情况是[0,i-1]中有多少个_x，第二种情况是以i结尾有多少个_x，第一种情况的个数就是更新前的f[x-'a']，第二种情况则需要知道[0,i-1]中有多少个字符和x不相同，这样才能组成_x。
求第二种情况需要再借助一个哈希表g[26]。
g[x-'a']的更新很简单，就是用更新前的g[x-'a']（更新前）+1。
知道了g[x-'a']，所以f[x-'a']=f[x-'a']（更新前）+i-g[x-'a']（更新前）。
3.初始化
不需要初始化，只需要把哈希表中的值初始化为0。
4.填表顺序
从左往右
5.返回值
结果就是把所以的dp[i]累加在一起，因为dp[i]==f[x-'a']，所以dp表其实可以不用创建，直接累加f即可。
代码：
#include <iostream> #include<string> using namespace std; int f[26]={0}; int g[26]={0}; int main() { int n; cin>>n; string s; cin>>s; long long ret=0; for(int i=0;i<n;i++) { int x=s[i]-'a'; ret+=f[x]; //更新f和g表 //要先更新f表，因为f表要用更新之前的g表 f[x]=f[x]+i-g[x]; g[x]=g[x]+1; } cout<<ret<<endl; }