1）兔子问题
2）青蛙跳台阶
3）青蛙变态跳台阶
4）1*2的长方形填满n*1的长方形问题
上述几个问题都是一样的，都属于斐波那契额数列问题
典型例题：合唱队问题：
思路：先正者求解最长递增序列，在将数组倒过来就最长递增序列，
#include <iostream> #include <map> #include <queue> #include<string> #include <sstream> #include <algorithm> using namespace std; int main() { int N=0; while(cin>>N) { int *a=(int*)malloc(N*sizeof(int)); for(int i=0;i<N;i++) cin>>a[i]; int*result1=(int*)malloc(N*sizeof(int)); for(int i=0;i<N;i++) result1[i]=1; for (int i=0;i<N;i++) { for (int j=i-1;j>=0;j--) { if (a[j]<a[i]&&result1[j]+1>result1[i]) { result1[i]=result1[j]+1; } } } int*result2=(int*)malloc(N*sizeof(int)); for(int i=0;i<N;i++) result2[i]=1; for (int i=N-1;i>=0;i--) { for (int j=i+1;j<N;j++) { if (a[j]<a[i]&&result2[j]+1>result2[i]) { result2[i]=result2[j]+1; } } } int max=0; int sum=0; for (int i=0;i<N;i++) { sum=result1[i]+result2[i]; if (sum>max) { max=sum; } } cout<<N-max+1<<endl; delete []a; delete[]result1; delete[]result2; } return 0; }
求解这个问题有两种解法，一种是
1）普通的三层循环
#include<vector> #include<iostream> #include<string> using namespace std; int main() { string str1; string str2; while(cin>>str1>>str2) { int max=0; for(int i=0;i=str1.size();i++) { for(int j=0;j<str2.size();j++) {
int m=i;
int k=j;
int temp=0;
while(str1[m]==str2[k])
{
m++;k++;temp++;
} if(temp>max) max=temp; } } cout<<max<<endl; } return 0; }
上面的程序指输出了最长子串的长度，若想输出最长子串是什么，只要记下最长子串的起点或终点既可以
下面的解法为动态规划解的，可以输出最长子串是什么，
2）
要求输出最长子串，而且有多个最长子串的时候，输出较短字符串中先出现的子串
#include<iostream> #include<string> #include<vector> using namespace std; int main() { string str1,str2; while(cin>>str1>>str2) { if(str1.size()<str2.size()) { str1.swap(str2); } int max=0; int idex=0; vector<vector<int> >res(str1.size()+1,vector<int>(str2.size()+1,-1)); vector<vector<string> >vec(str1.size()+1,vector<string>(str2.size()+1,"")); for(int i=1;i<=str1.size();i++) { for(int j=1;j<=str2.size();j++) { if(str1[i-1]==str2[j-1]) { vec[i][j]=vec[i-1][j-1]+str1[i-1]; if(vec[i-1][j-1].size()>0) res[i][j]=res[i-1][j-1]; else res[i][j]=j-1; } else { vec[i][j]=""; } if(vec[i][j].size()>=max) { if(vec[i][j].size()>max) { idex=res[i][j]; max=vec[i][j].size(); } else { if(idex>res[i][j]) idex=res[i][j]; } } } } for(int i=idex;i<idex+max;i++) cout<<str2[i]; cout<<endl; } return 0; } 若想输出所有的最长公共子串，则上述代码不需要记录idex,只记录vec[i][j]即可，即以str1[i]str2[j]结尾的最长子串，然后遍历vec,输出最长的
也可以记录最长的子串出现的idex号，然后根据长度来输出
与最长子串来讲，此题用动态规划来做
#include <iostream> #include <string> using namespace std; int main(int argc, char **argv) { string str1 = "ABCBDAB"; string str2 = "BDCABA"; int x_len = str1.length(); int y_len = str2.length(); int arr[50][50] = {{0,0}}; int i = 0; int j = 0; for(i = 1; i <= x_len; i++) { for(j = 1; j <= y_len; j++) { if(str1[i - 1] == str2[j - 1]) { arr[i][j] = arr[i - 1][j - 1] + 1; } else { if(arr[i][j - 1] >= arr[i - 1][j]) { arr[i][j] = arr[i][j - 1]; } else { arr[i][j] = arr[i -1][j]; } } } } cout<<arr[x_len][y_len]<<endl; } 此题目还需要有一个注意的是：如何输出所有的最长子序列(对于输出所有的最长子串来说是比较容易的，因为子串连续，子序列不连续）下面讲解如何输出所有的最长子序列输出一个最长公共子序列并不难（网上很多相关代码），难点在于输出所有的最长公共子序列，因为 LCS 通常不唯一。总之，我们需要在动态规划表上进行回溯 —— 从table[m][n]，即右下角的格子，开始进行判断：
如果格子table[i][j]对应的X[i-1] == Y[j-1]，则把这个字符放入 LCS 中，并跳入table[i-1][j-1]中继续进行判断；
如果格子table[i][j]对应的 X[i-1] ≠ Y[j-1]，则比较table[i-1][j]和table[i][j-1]的值，跳入值较大的格子继续进行判断；
直到 i 或 j 小于等于零为止，倒序输出 LCS 。
如果出现table[i-1][j]等于table[i][j-1]的情况，说明最长公共子序列有多个，故两边都要进行回溯（这里用到递归）。
// 动态规划求解并输出所有LCS #include <iostream> #include <string> #include <vector> #include <set> using namespace std; string X = "ABCBDAB"; string Y = "BDCABA"; vector<vector<int>> table; // 动态规划表 set<string> setOfLCS; // set保存所有的LCS int max(int a, int b) { return (a>b)? a:b; } /** * 字符串逆序 */ string Reverse(string str) { int low = 0; int high = str.length() - 1; while (low < high) { char temp = str[low]; str[low] = str[high]; str[high] = temp; ++low; --high; } return str; } int lcs(int m, int n) { // 表的大小为(m+1)*(n+1) table = vector<vector<int>>(m+1,vector<int>(n+1)); for(int i=0; i<m+1; ++i) { for(int j=0; j<n+1; ++j) { // 第一行和第一列置0 if (i == 0 || j == 0) table[i][j] = 0; else if(X[i-1] == Y[j-1]) table[i][j] = table[i-1][j-1] + 1; else table[i][j] = max(table[i-1][j], table[i][j-1]); } } return table[m][n]; } /** * 求出所有的最长公共子序列，并放入set中 */ void traceBack(int i, int j, string lcs_str) { while (i>0 && j>0) { if (X[i-1] == Y[j-1]) { lcs_str.push_back(X[i-1]); --i; --j; } else { if (table[i-1][j] > table[i][j-1]) --i; else if (table[i-1][j] < table[i][j-1]) --j; else // 相等的情况 { traceBack(i-1, j, lcs_str); //语句1 traceBack(i, j-1, lcs_str); //语句2 return; } } } setOfLCS.insert(Reverse(lcs_str)); } int main() { int m = X.length(); int n = Y.length(); int length = lcs(m, n); cout << "The length of LCS is " << length << endl; string str; traceBack(m, n, str); set<string>::iterator beg = setOfLCS.begin(); for( ; beg!=setOfLCS.end(); ++beg) cout << *beg << endl; getchar(); return 0; }
此处只是简单介绍连个回文的题目
1判断一个字符串的最长回文子串多长
网上有很多关于磁体的解法，但是看起来比较复杂，就没有看，然后自己想了一种用动态规划做的，可能时间复杂度比较高
1）先将一直字符串逆序，形成了两个字符串，
2）求取两个字符串的最长公共子串，但是每求出一个公共子串要返回去验证是否是回文
#include<iostream> #include<string> using namespace std; int Judge_if_real(string str,int i,int temp) { string s; for(int j=i,k=i+temp-1;j<=k;j++,k--) { if(str[j]!=str[k]) return 0; } return 1; } int main() { string str1; while(cin>>str1) { string str2; for(int i=str1.size()-1;i>=0;i--) { str2+=str1[i]; } int max=0; int idex=0; for(int i=0;i<str1.size();i++) { for(int j=0;j<str2.size();j++) { if(str1[i] == str2[j]) { int m=i; int k=j; int temp=0; while(m<str1.size()&&k<str2.size()&&str1[m]==str2[k]) { m++; k++; temp++; } if(temp>max&&Judge_if_real(str1,i,temp)) { max=temp; } } } } cout<<max<<endl; } return 0; }2）判断最少删除几个字符，使得字符串变成最长回文字符串
此题即为求取字符串和字符串逆序的最长公共自序列
1）0—1背包问题
2）完全背包问题
有n种物品，每种物品有无限个，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为total，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？
与上面0——1背包的区别就是，每个物品有无数个，那么到后续在需要放进背包的时候可以是任何一一个
1） 子问题定义：F[i][j]表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。
2） 根据第i种物品放多少件进行决策
(2-1)
其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品；
空间复杂度O(VN)、时间复杂度为O(NV∑(j/C[i]))
for（int i=1;i<=N;i++) { for(int j=1;j<=m;j++) { int temp=F[i-1][j]]; for(int k=1;k<j./w[i];k++) { if(temp<F[i-1][j-k*w[i]]+k*w[i]; temp=F[i-1][j-k*w[i]]+k*w[i]; } F[i][j]=tenmp; } }
问题简化1
设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。如果不放那么F[i][j]=F[i-1][j]；如果确定放，背包中应该出现至少一件第i种物品，所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]？因为F[i][j-C[i]]里面可能有第i种物品，也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品，所以要预留C[i]的空间来存放一件第i种物品。
状态方程为：
for（int i=1;i<=N;i++)
{
for(int j=1;j<=m;j++)
{
int temp=0;
if(j>w[i])
temp=F[i][j-w[i]]+v[i];
F[i][j]=max(F[i-1][j],temp);
}
}
时间复杂度优化为O(NV)3）多重背包问题
此问题与完全背包的问题比较相似
有N种物品和一个容量为V的背包。第i种物品最多有num[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装
入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
分析：状态转移为：
程序需要求解N*V个状态，每一个状态需要的时间为O（v/Weight[i]），总的复杂度为O(NV*Σ(V/Weight[i]))。
for（int i=1;i<=N;i++) { for(int j=1;j<=m;j++) { int temp=F[i-1][j]; for(int k=1;k<j./w[i]&&k<num[i];k++) { if(temp<F[i-1][j-k*w[i]]+k*w[i]; temp=F[i-1][j-k*w[i]]+k*w[i]; } F[i][j]=tenmp; } }
七、动态规划的应用
1）请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
解析：
#include<iostream> #include<vector> using namespace std; int main() { int n,m; while(cin>>n>>m) { vector<vector<int>>vec(n+1,vector<int>(m+1,0)); for(int i=0;i<n+1;i++) vec[i][0]=1; for(int i=0;i<m+1;i++) vec[0][i]=1; for(int i=1;i<n+1;i++) { for(int j=1;j<m+1;j++) { vec[i][j]=vec[i-1][j]+vec[i][j-1]; } } cout<<vec[n][m]<<endl; } return 0; }2)字符串的距离或计算字符串的相似度
#include<iostream> #include<string> #include<vector> using namespace std; int main() { string str1,str2; while(cin>>str1>>str2) { if(str1.size()<=0) { cout<<1<<"/"<<str2.size()+1<<endl; continue; } if(str2.size()<=0) { cout<<1<<"/"<<str1.size()+1<<endl; continue; } vector<vector<int> >res(str1.size()+1,vector<int>(str2.size()+1,0)); for(int i=0;i<=str1.size();i++) { res[i][0]=i; } for(int i=0;i<=str2.size();i++) { res[0][i]=i; } for(int i=1;i<=str1.size();i++) { for(int j=1;j<=str2.size();j++) { if(str1[i-1]==str2[j-1]) { res[i][j]=res[i-1][j-1]; } else { res[i][j]=min(res[i-1][j]+1,min(res[i][j-1]+1,res[i-1][j-1]+1)); } } } cout<<1<<"/"<<res[str1.size()][str2.size()]+1<<endl; } return 0; } 注意：此文中关于背包的动态规划问题值讲解了基础解析，下次大背包问题的简化
