斐波那契数列 （动态规划的递归写法）
#include <iostream>
#include <vector>
using namespace std;
vector<int> dp(1000);
int F(int n) {
if (n == 0 || n == 1) return 1;
if (dp[n] != -1) return dp[n];
else
{
dp[n] = F(n - 1) + F(n - 2);
return dp[n];
}
}
int main() {
fill(dp.begin(), dp.end(), -1);
cout << F(5)<<endl;
return 0;
}
// 得打断点 去好好理解下这个递归和动态规划的流程
数塔问题 (动态规划的递推写法)
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005][1005];
int f[1005][1005];
int main() {
//int dp[1005][1005];
//int f[1005][1005];
//神奇，为什么把二维数组的声明放这里会报错。
fill(dp[0], dp[0] + 1005 * 1005, 0);
fill(f[0], f[0] + 1005 * 1005, 0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++){
cin >> f[i][j];
}
}
for (int i = 1; i <= n; i++)
{
dp[n][i] = f[n][i];
}
for (int i = n-1; i >=1; i--)
{
for (int j = 1; j <= i; j++)
{
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
}
}
cout << dp[1][1]<<endl;
return 0;
}
图片.png
最大连续子序列和
#include <iostream>
#include <algorithm>
using namespace std;
int dp[10005];
int A[10005];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
dp[0] = A[0];
for (int i = 1; i < n; i++)
{
dp[i] = max(A[i], dp[i - 1] + A[i]);
}
int index = 0;
for (int i = 1; i < n; i++) {
if (dp[i]> dp[index])
{
index = i;
}
}
cout << dp[index]<<endl;
return 0;
}
最长不下降子序列
#include <iostream>
#include <algorithm>
using namespace std;
int A[10005];
int dp[10005];
int main() {
int N;
cin >> N;
for(int i=0;i<N;i++){
cin>>A[i];
}
int ans = -1;
for(int i=0;i<N;i++){
dp[i] = 1;
for(int j=0; j<i;j++){
if(A[j]<=A[i] && dp[i]<dp[j]+1){
dp[i] = dp[j] + 1;
}
}
ans = max(ans,dp[i]);
}
cout << ans<<endl;
return 0;
}
最长公共子序列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
char A[N], B[N];
int dp[N][N];
int main() {
int n;
gets_s(A + 1,95);
// 而fgets会存储换行符
gets_s(B + 1,95);
int lenA = strlen(A+1);
int lenB = strlen(B+1);
for (int i = 0; i <= lenA; i++)
{
dp[i][0] = 0;
}
for (int i = 0; i <= lenB; i++)
{
dp[0][i] = 0;
}
for (int i = 1; i <= lenA; i++)
{
for (int j = 1; j <= lenB; j++)
{
if (A[i] == B[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[lenA][lenB];
return 0;
}
最长公共子序列.png
最长回文子串
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100;
char S[maxn];
int dp[maxn][maxn];
int main() {
int n;
gets(S);
// 而fgets会存储换行符
int len = strlen(S),ans = 1;
memset(dp, 0, sizeof(dp));//dp数组初始化为0
//边界
for (int i = 0; i < len; i++)
{
dp[i][i] = 1;
if (i < len - 1) {
if (S[i] == S[i + 1]) {
dp[i][i + 1] = 1;
ans = 2;
}
}
}
for (int L = 3; L <= len; L++){ //枚举子串的长度
for (int i = 0; i+L-1 < len; i++){ //枚举子串的起始端点
int j = i + L - 1;
if (S[i] == S[j] && dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
ans = L;
}
}
}
cout << ans;
return 0;
}
DAG最长路
1.求整个DAG中的最长路径(即不固定起点跟终点)
const int INF = 1e9;
const int n = 1e3;
int dp[n] = { 0 };
// dp[i]表示从i号顶点出发能获得的最长路径长度
// 出度为0的顶点会返回dp[i]= 0
int G[n][n]; //用邻接矩阵来存储图，初始化为INF
int choice[n]; //记录最长路径上顶点的后继顶点，初始化为-1
int DP(int i) {
if (dp[i] > 0) return dp[i]; //dp[i]已计算得到
for (int j = 0; j < n; j++) //遍历i的所有出边
{
if (G[i][j] != INF) {
int temp = DP(j) + G[i][j]; // 单独计算，防止if中调用DP函数两次
if (temp > dp[i]) { //可以获得更长的路径
dp[i] = temp; //覆盖dp[i]
choice[i] = j; //i号顶点的后继顶点是j
}
}
}
return dp[i];// 返回计算完成的dp[i]
}
// 调用printPath前需要先得到最大的dp[i],然后将i作为路径起点传入
int printPath(int i) {
printf("%d", i);
while (choice[i] != -1)
{
i = choice[i];
printf("->%d", i);
}
}
//以上代码自动实现了如果DAG中有多条最长路径，选取字典序最小的那条
//可是如果令dp[i]表示以i号顶点结尾能获得的最长路径长度，如此操作，却无法直接得到字典序最小的那条。
--------------------------
2.固定顶点，求DAG的最长路径
int dp[n] = -INF; //dp[T]=0 表示终点的边界，所以dp[i]不能再初始化为0，应该初始化为-INF代表“无法到达终点”
bool vis[n] ;// 初始化为false。此数组表示顶点是否已经被计算
int DP(int i) {
if (vis[i]) return dp[i];
vis[i] = true;
for (int j = 0; j < n; j++)
{
if (G[i][j] != INF) {
dp[i] = max(dp[i], DP（j）+ G[i][j]);
}
}
return dp[i];
}
01背包问题
网友评论