当属性是最大值或者最小值的时候，划分子问题可以有重复的部分，但是如果求元素的数量，那么划分子问题不能有重复的部分
常用模型：背包
优化的时候，如果用上一层体积，就从大到小枚举，如果用本层体积，就从小到大枚举
01背包 --每件物品最多只用一次
const N int = 1010
func knapsack01(N []int,m int) int{
n := len(N)
//dp[i][j]表示选取前i件物品且背包容量为j时，背包中物品的最大价值
var dp [][]int = make([][]int,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
for i := 1 ; i < n ; i++ {
for j := 0 ; j <= m ; j++ {
dp[i][j] = dp[i-1][j]
if(j >= v[i]){
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i])
}
}
}
return dp[n][m]
}将其优化成一维
func knapsack01(N []int,m int) int{
n := len(N)
var dp []int = make([]int,m+1)
for i := 1 ; i < n ; i++ {
for j := m ; j >= v[i] ; j-- {
dp[j] = max(dp[j],dp[j-v[i]]+w[i])
}
}
return dp[m]
}完全背包--每件物品使用次数没有限制（枚举第i个物品选几个）
func completeBackpack(N []int,m int) int {
n := len(N)
var dp [][]int = make([][]int ,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
for i := 1 ; i <= n ; i++ {
for j := 0 ; j <= m ; j++ {
for k := 0 ; k * v[i] <= j ; k++ {
dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])
}
}
}
return dp[n][m]
}优化后的完全背包问题-优化成二维
func completeBackpack(N []int,m int) int {
n := len(N)
var dp [][]int = make([][]int ,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
for i := 1 ; i <= n ; i++ {
for j := 0 ; j <= m ; j++ {
dp[i][j] = dp[i-1][j]
if j >= v[i] {
dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i])
}
}
}
return dp[n][m]
}优化成一维
func completeBackpack(N []int,m int) int {
n := len(N)
var dp []int = make([]int ,m+1)
for i := 1 ; i <= n ; i++ {
for j := v[i] ; j <= m ; j++ {
dp[j] = max(dp[j],dp[j-v[i]]+w[i])
}
}
return dp[m]
}多重背包问题 --每种物品最多有Si个
func completeBackpack(N []int,m int,s []int) int {
n := len(N)
var dp [][]int = make([][]int ,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
for i := 1 ; i <= n ; i++ {
for j := 0 ; j <= m ; j++ {
for k := 0 ; k <= s[i] && k * v[i] <= j ; k++ {
dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])
}
}
}
return dp[n][m]
}使用二进制的方式进行优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;//从1开始分，只要k<=s，每次把k个第i个物品打包在一起
while (k <= s)
{
cnt ++ ;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0) //把最后剩下的s个物品组到一块
{
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}分组背包问题 --物品有N组，每一组物品有若干个，每组里面最多只能选一个物品（枚举第i组物品选哪个）
func groupBackpack(v [][]int,w [][]int,s []int ,m int){
n := len(v)
var dp []int = make([]int,n+1)
for i := 0 ; i <= n ; i++{
dp[i] = make([]int,m+1)
}
for i := 1 ; i <= n ; i++ {
for j := 0 ; j <= 0 ; j++ {
for k := 0 ; k < s[i] ; k ++{
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]]+w[i][k])
}
}
}
return dp[n][m]
}func groupBackpack(v [][]int,w [][]int,s []int ,m int){
n := len(v)
var dp []int = make([]int,m+1)
for i := 1 ; i <= n ; i++ {
for j := m ; j >= 0 ; j-- {
for k := 0 ; k < s[i] ; k ++{
dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k])
}
}
}
return dp[m]
}不同类型DP
线性DP
func maximumTotal(triangle [][]int) int {
if len(triangle) == 0 || len(triangle[0]) == 0 {
return 0
}
n := len(triangle)
var dp [][]int = make([][]int,n)
for i := 0 ; i < n ; i ++ {
dp[i] = make([]int,len(triangle[i]))
}
dp[0][0] = triangle[0][0]
for i := 1 ; i < n ; i ++ {
for j := 0 ; j <= i;j++ {
if j == 0 {
dp[i][j] = dp[i-1][j]+triangle[i][j]
}else if j == i {
dp[i][j] = dp[i-1][j-1]+triangle[i][j]
}else {
dp[i][j] = max(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j])
}
}
}
sort.Ints(dp[n-1])
m := len(dp[n-1])
return dp[n-1][m-1]
}
func max(a,b int) int{
if a > b {
return a
}
return b
}优化之后
func maximumTotal(triangle [][]int) int {
if len(triangle) == 0 || len(triangle[0]) == 0 {
return 0
}
n := len(triangle)
var dp []int = make([]int,n)
dp[0] = triangle[0][0]
for i := 1 ; i < n ; i ++ {
for j := i ; j >= 0;j-- {
if j == 0 {
dp[j] = dp[j]+triangle[i][j]
}else if j == i {
dp[j] = dp[j-1]+triangle[i][j]
}else {
dp[j] = max(dp[j]+triangle[i][j],dp[j-1]+triangle[i][j])
}
}
}
sort.Ints(dp)
return dp[n-1]
}
func max(a,b int) int{
if a > b {
return a
}
return b
}
//dp[i]表示所有以i结尾的上升子序列的最大长度
func lengthOfLIS(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
var dp []int = make([]int,n)
for i := 0 ; i < n ; i++{
dp[i] = 1
}
for i := 0 ; i < n ; i++ {
for j := 0 ; j < i ; j++{
if nums[i] > nums[j]{
dp[i] = max(dp[i],dp[j]+1)
}
}
}
sort.Ints(dp)
return dp[n-1]
}
func max(a,b int)int {
if a > b {
return a
}
return b
}用来输出最长上升子序列
时间复杂度的优化O(nlongn)
func longestCommonSubsequence(text1 string, text2 string) int {
n := len(text1)
m := len(text2)
var dp [][]int = make([][]int,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
text1 = " " + text1
text2 = " " + text2
for i := 1 ; i < n + 1 ; i++ {
for j := 1 ; j < m + 1 ; j++ {
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
if text1[i] == text2[j] {
dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)
}
}
}
return dp[n][m]
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
//dp[i][j]表示从word1[1..i]到word2[1..j]需要的最少操作数
func minDistance(word1 string, word2 string) int {
n := len(word1)
m := len(word2)
word1 = " " + word1
word2 = " " + word2
dp := make([][]int,n+1)
for i := 0 ; i <= n ; i++ {
dp[i] = make([]int,m+1)
}
for i := 0 ; i <= n ; i++ {
dp[i][0] = i
}
for i := 0 ; i <= m ; i++ {
dp[0][i] = i
}
for i := 1 ; i <= n ; i++{
for j := 1 ; j <= m ; j++ {
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1)
t := 0
if word1[i] != word2[j]{
t = 1
}
dp[i][j] = min(dp[i][j],dp[i-1][j-1]+t)
}
}
return dp[n][m]
}
func min(a,b int)int{
if a < b {
return a
}
return b
}区间DP问题
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 2 堆石头合并为一堆，而这个移动的成本为这 2 堆石头的总数。
找出把所有石头合并成一堆的最低成本。
func miniMumCost(stone []int) int {
n := len(stone)
//用来求前缀和
var s []int = make([]int,n)
s[0] = stone[0]
for i := 1 ; i < n ; i++ {
s[i]=s[i-1]+a[i]
}
var dp [][]int = make([][]int,n)
for i := 0 ; i < n ; i++ {
dp[i] = make([]int,n)
}
for i := 1 ; i < n ; i++ {
for j := 0 ; j + i -1 < n ; j++{
l,r:=j,j+i-1
dp[l][r] = 1e8
for k := l ; k < r ; k++ {
dp[l][r] = min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1])
}
}
}
return dp[0][n-1]
}数位统计DP
计数问题
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc
1. num[i] < x, 0
2. num[i] == x, 0~efg
3. num[i] > x, 0~999
*/
int get(vector<int> num, int l, int r)
{
int res = 0;
for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
return res;
}
int power10(int x)
{
int res = 1;
while (x -- ) res *= 10;
return res;
}
int count(int n, int x)
{
if (!n) return 0;
vector<int> num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size();
int res = 0;
for (int i = n - 1 - !x; i >= 0; i -- )
{
if (i < n - 1)
{
res += get(num, n - 1, i + 1) * power10(i);
if (!x) res -= power10(i);
}
if (num[i] == x) res += get(num, i - 1, 0) + 1;
else if (num[i] > x) res += power10(i);
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b , a)
{
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i ++ )
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}状态压缩DP
蒙德里安的梦想
代码主要分为两个部分（横着摆放的方式确定后，竖着摆放的方式就已确定）：
枚举每一列合法的占位方式，记录在str数组内
（把连续空格数为奇数的状态设定为false，因为空格要摆放竖着的方块，单个空格无法摆放方块）
开始DP
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;//M的每一位二进制位储存一种状态
int n, m;
long long f[N][M];
bool st[M];//储存每一列上合法的摆放状态
//f[i][j]表示摆放第i列，i列向后伸出来横着的方格状态为j的方案数，j为一个二进制数，用01表示是否戳出来
int main()
{
while (cin >> n >> m, n || m)
{
//枚举每一列的占位状态里哪些是合法的
for (int i = 0; i < 1 << n; i ++ )//一共n行，枚举n位不同的状态
{
int cnt = 0;//用来记录连续的0的个数
st[i] = true;//记录这个状态被枚举过且可行
for (int j = 0; j < n; j ++ )//从低位到高位枚举它的每一位
if (i >> j & 1)//如果为1
{
if (cnt & 1) st[i] = false;//如果之前连续0的个数是奇数，竖的方块插不进来，这种状态不行
cnt = 0;//清空计数器
}
else cnt ++ ;//如果不为1，计数器+1
if (cnt & 1) st[i] = false;//到末尾再判断一下前面0的个数是否为奇数，同前
}
memset(f, 0, sizeof f);//一定要记得初始化成0，对于每个新的输入要重新计算f[N][M]
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )//对于每一列
for (int j = 0; j < 1 << n; j ++ )//枚举j的状态
for (int k = 0; k < 1 << n; k ++ )//再枚举前一行的伸出状态k
if ((j & k) == 0 && st[j | k])//如果它们没有冲突，i这一列被占位的情况也是合法的话
f[i][j] += f[i - 1][k];//那么这种状态下它的方案数等于之前每种k状态数目的和
cout << f[m][0] << endl;//求的是第m行排满，并且第m行不向外伸出块的情况
}
return 0;
}最短Hamilton路径
题目描述
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤201≤n≤20
0≤a[i,j]≤1070≤a[i,j]≤107
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
#include <bits/stdc++.h>
using namespace std;
int n,f[1<<20][21],i,j,k;
int weight[21][21];
int main()
{
ios::sync_with_stdio(false);//加快cin的读入速度，但是scanf将会不能用。
memset(f,0x3f,sizeof(f));//初始化最大值
cin>>n;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
cin>>weight[i][j];
f[1][0]=0;//第一个点是不需要任何费用的
for (i=1; i<(1<<n); i++)//i代表着是一个方案集合，其中每一个位置1和0，代表着这个点经过还是没有经过
for (j=0; j<n; j++)//枚举当前到了哪一个点
if ((i>>j & 1))//如果i集合中第j位是1，也就是到达过这个点
for (k=0; k<n; k++)//枚举到达j的点k
if ((i^(1<<j)) >> k & 1)//重点，判断k和j的条件，具体在上面解说
f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);//选择最小值，也就是判断，k点到j点最优，还是以前的方案最优
cout<<f[(1<<n)-1][n-1];//输出最后的最优值
return 0;
}树形DP
没有上司的舞会
Ural大学有N名职员，编号为1~N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数N。
接下来N行，第 i 行表示 i 号职员的快乐指数Hi。
接下来N-1行，每行输入一对整数L, K,表示K是L的直接上司。
最后一行输入0,0。
输出格式
输出最大的快乐指数。
数据范围
1≤N≤6000,
−128≤Hi≤127
样例 输入样例： 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6010;
int n;
int h[N], e[N], ne[N], idx;//因为树可以看做特殊的图，所以用邻接表来存储树
int happy[N];//每个人的高兴度
int f[N][2];//所有状态
bool has_fa[N];//判断每个点是否有父节点
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
f[u][1] = happy[u];//如果选择这个点就需要加上其高兴度
for (int i = h[u]; ~i; i = ne[i])//枚举u的所有儿子
{
int j = e[i];//u的某个儿子
dfs(j);
f[u][1] += f[j][0];
f[u][0] += max(f[j][0], f[j][1]);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(b, a);//在邻接表中插入这条边
has_fa[a] = true;
}
int root = 1;
while (has_fa[root]) root ++ ;
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}记忆化搜索
滑雪
func slide(h [][]int) int{
n := len(h)
m := len(h[0])
var f [][]int = make([][]int,n)
for i := 0 ; i < n ; i++ {
f[i] = make([]int,m)
}
dx := []int{-1,0,1,0}
dy := []int{0,1,0,-1}
var dp func(int,int) int
dp = func(x int,y int)int{
if f[x][y] != 0 {return f[x][y]}
f[x][y] := 1
for i := 0 ; i < 4 ; i++ {
a := x + dx[i]
b := y + dy[i]
if a >= 0 && a < n && b >=0 && b < m && h[a][b] < h[x][y] {
f[x][y] = max(f[x][y],dp(a,b)+1)
}
}
return f[x][y]
}
res := 0
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
res = max(res,dp(i,j))
}
}
return res
}
京公网安备 11010502036488号