Algorithm2.9 dp思维
[TOC]
思维 & dp
Leetcode1578-valid-palindrome
题目大意：
1、结合贪心思想，永远把相邻的最小的给加进去，ans += min(cost[i-1], cost[i])
2、状态的推进更新，例如str="aaa"，cost分别为4 3 5，在更新4 3时候就要把状态退后，用这两个的最大的去比【因为最大的才是真正留下来的】，所以要用cost[i] = max(cost[i-1], cost[i])来保留状态
int minCost(string s, vector<int>& cost) {
int ans = 0;
for (int i = 1; i < s.length(); i++){
if (s[i] == s[i-1]){
ans += min(cost[i-1], cost[i]);
cost[i] = max(cost[i-1], cost[i]);
}
}
return ans;
}
「循环」一圈形式的dp
https://www.luogu.com.cn/problem/P1057
题目大意：
#include <iostream>
using namespace std;
#define maxn 32
int n, t, dp[maxn][maxn]; // dp[i][j]表示第i次传球第j个人到自己手上的方式总数
// 初始化：第一次也就是第一个人是1，其他都是0。也就是dp[0][0] = 1
// 状态转移：某人某次传球到自己手上的方式总数是在上一次传到两个旁边的人手上之和
// dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1] (注意对圈的边界的人的特判)
int main() {
scanf("%d%d", &n, &t);
// init
dp[0][0] = 1;
for (int i = 1; i < t; ++i)
for (int j = 0; j < n; ++j)
if (j == 0) dp[i][j] = dp[i-1][1]+dp[i-1][n-1];
else if (j == n-1) dp[i][j] = dp[i-1][n-2]+dp[i-1][0];
else dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1];
printf("%d\n", dp[t-1][0]);
return 0;
}
「回文」判断最长回文串
bool dp[i][j]表示从[i,j]这一段是否为回文串- 状态转移方程：
dp[i][j] = (s[i] == s[j] && (j-i == 1||dp[i+1]dp[j-1]))?true:false (j > i) - j-i == 1 是对aa这种两个字符呈对称形式的情况
//
// main.cpp
// 5回文子串
//
// Created by 陈冉飞 on 2020/4/6.
// Copyright © 2020 陈冉飞. All rights reserved.
//
#include <iostream>
using namespace std;
#define maxn 10010
char s[maxn];
int main(int argc, const char * argv[]) {
scanf("%s",s);
int len = strlen(s),ans = 0;
bool dp[len][len];
for (int i = 0; i < len; i++) dp[i][i] = true;
for (int j = 1; j < len; j++)
for (int i = 0; i < j; i++)
if (s[i] == s[j] && (j-i == 1 || dp[i+1][j-1])) {dp[i][j] = true;ans = max(ans,j-i+1);}
else dp[i][j] = false;
printf("%d\n",ans);
return 0;
}
「回文」以回文串形式抽取字串的最小次数
- dp[i][j]表示区间[i,j]的最少抽取次数
- 状态转移方程
if (s[i] == s[j]) dp[i][j] = (j-i == 1)?1:dp[i+1][j-1]dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j])
//
// main.cpp
// 区间dp_最少删的回文子串_cf607B
//
// Created by 陈冉飞 on 2019/8/12.
// Copyright © 2019 陈冉飞. All rights reserved.
//
#include <iostream>
using namespace std;
#include <cstring>
#define cl(a,b) memset(a,b,sizeof(a))
#include <string>
#define maxn 505
int dp[maxn][maxn],a[maxn]; //dp[i][j]表示i-j这段区间合并所需要的次数 a是储存的原来的
int n,len,i,j,k; //j是起点加上重点的位置，然后k是这段区间中第一段分割的长度
#define INF 0x3f3f3f
int main(int argc, const char * argv[]) {
scanf("%d",&n);
cl(dp, INF);
for (i = 1; i <= n; i++) {
scanf("%d",&a[i]);
dp[i][i] = 1;
}
for (len = 1; len < n; len++) //先遍历长度，在遍历起点
for (i = 1; i+len <= n; i++) {
j = i+len;
if (a[i] == a[j])
dp[i][j] = len == 1?1:dp[i+1][j-1];
for (k = i; k < j; k++) dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]); //从中间找切断点k
}
// for (i = 2; i <= n; i++) cout<<i<<" "<<dp[1][i]<<endl;
cout<<dp[1][n]<<endl;
return 0;
}