动态规划

买四类票,求最小的花费

小明相要出去玩,提供了一年出去玩的具体天数,然后他可以买1,3,7,30日票,每种票管辖的时间不一样,票价不一样,现在求出最小花费

//dp[i] 代表的是截至当天 最小的花费
for(int i = 1;i<=365;i++)
{
	if(当天旅游)
	{
		for j in 4:
			dp[i] = min{dp[i-day[j]] + cost[j]};
			//相当于在前面找一个最省钱的一天
	}else{
		dp[i] = dp[i-1]//不旅游就和上一天相同
	}
}

由平方数组成的最小个数

一个数可以由进行加减运算得到,现在给你一个数,求出他由最少个数的平方数组成

//dp[i] 代表组成i这个数字所需要的最小个数 将每个数的最少组成个数都求出来
//注意一个数有可能通过加上一个平方数得到的也有可能通过减去一个平方数得到的
for i in 1e5:
	for j*j<=i:
	//遍历所有可能平方数 找到最优结果
		dp[i] = min(dp[i],dp[i-j*j]+1)
		//答案也有可能在后面
		if i+j*j<1e5:
			dp[i] = min(dp[i],dp[i+j*j])

01背包问题

一个物品有价值,有重量,求总重量不超过一个极限的情况下的最大价值

//dp[i][v] 表示的是前i件物品放入容量为v的最大价值
//dp[i][v] = max(dp[i-1][v] + dp[i][v-w[i]]+cost[i])
//就是在选与不选之间徘徊一个最大的
for(int i = 1;i<=N;i++)// 遍历N件物品
{
    for(int v = w[i];v<=V;v++)
    {
        dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]]+cost[i]);
    }
}

完全背包问题

一个物体有价值,有重量,数量无限,求总重量不超过一个范围的最大价值

//dp[i][v] 表示的是前i件物品放入容量为v的最大价值
//dp[i][v] = max(dp[i-1][v] + dp[i][v-w[i]]+cost[i])
//就是在选与不选之间徘徊一个最大的 
//和01代码区别在于 假如选了一次还能再选一次 所以转移还是i
for(int i = 1;i<=N;i++)// 遍历N件物品
{
    for(int v = w[i];v<=V;v++)
    {
        dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]]+cost[i]);
    }
}

过河卒

求从原点到这个点的路径个数,中间有的点过不去

//dp[i][j]的含义为从起点到该点的路径个数
for(int i = 0;i<=a;i++)
{
    for(int j = 0;j<=b;j++)
    {
        if(vis[i][j]!=false)
        {
            dp[i][j] = dp[i-1]+dp[j-1];
        }
    }
}

最长上升子序列问题 LIS

给你一个字符串或者数组,在里面找到一串上升的子序列,要求最长的长度

//dp[i]的含义为以i结尾的最长上升序列 
//由于是以i结尾的最大值 所以有可能最大值在中间序列产生
//字符串从1开始计数
for(int i = 2;i<=N;i++)
{
    for(int j = 1;j<i;j++)
    {
        if(num[i]>num[j])
        {
            dp[i] = max(dp[i],dp[j]+1);
        }
    }
    ans= max(ans,dp[i]);
}

最长公共子序列 LCS

给定两个字符串,求出两个字符串公共的最长的子串长度

//dp[i][j] 表示第一个串结尾为i,第二个串结尾为j的最长公共序列
for(int i = 1;i<=n;i++)
{
    for(int j = 1;j<=m;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]);
        }
    }
    ans = max(ans,dp[i][j]);
}

合成台概率问题

有A个原料,每B个可以合成一个产品,每次合成可以选择其中一个.

的概率双倍合成

的概率返回一个原材料

求出期望合成的产物,下面分析一下

设置代表剩余i个材料时可以合成的最大期望值

然后下面就根据这个假设不断的推演就可以了

//1. P的概率用B个材料合成两个产品，（1-P）的概率用B个材料合成一个产品。
//dp[i] = P*(dp[i-B]+2) + (1-P)*(dp[i-B]+1)
//2. Q的概率只需要（B-1）个材料合成一个产品 ，（1-Q）的概率用B个材料合成一个产品。
//dp[i] = Q*(dp[i-B+1]+1) + (1-Q)*(dp[i-B]+1)
//每次选择都在两者取最大值 需要注意当B为1的时候上述需要改变
for(int i = 1;i<=A;i++)
{
    dp[i] = max(Q*(dp[i-B+1]+1) + (1-Q)*(dp[i-B]+1),
                P*(dp[i-B]+2) + (1-P)*(dp[i-B]+1));
}

记忆化搜索

在地图中寻找最长下降序列的长度,路径可上下左右

/*
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
例如这个最长距离从25开始,然后依次可以寻找到最长为25
主要的思路就是设置一个dp[i][j] 表示从<i,j>开始的最长长度 然后后面在此基础上进行叠加即可
最需要注意的是 范围问题 其次是记住 每次加一个最大的 是在四个方位中比较出来最大的加上
*/

#include <bits/stdc++.h>
using namespace std;

int mp[305][305];
int r,c;
//以这个为起点的最长距离
int dp[305][305];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

//以这个点的最长距离
int slove(int x,int y)
{
    if(dp[x][y]>1)return dp[x][y];
    int mx = 0;
    for(int i = 0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(mp[nx][ny]<mp[x][y] && nx>=1 && ny>=1 && nx<=r && ny <= c)//可以接力下去 找一个最大的
        {
            mx = max(mx,slove(nx,ny));
        }
    }
    dp[x][y] += mx;
    return dp[x][y];
}

int main()
{
    cin >> r >> c;
    for(int i = 1;i<=r;i++)
    {
        for(int j = 1;j<=c;j++)
        {
            cin >> mp[i][j];
            dp[i][j] = 1;//表示本身距离为1
        }
    }
    int mx = 0;
    for(int i = 1;i<=r;i++)
    {
        for(int j = 1;j<=c;j++)
        {
            mx = max(mx,slove(i,j));
        }
    }
    cout << mx;
    return 0;
}

树形dp

最经典的一道题,没有上司的舞会,给你一棵树,每个树上都有一个权值,不能直接的选父亲和孩子,寻找最大的权值和

/*
分为两种状体 注意分析题目 
如果不选当前结点 就可以选择所有的孩子结点
dp[x][0] = sum{max(dp[j][0],dp[j][1])}

如果选择当前结点 也是累加所有不选孩子的情况
dp[x][1] = sum{dp[j][0]}
注意记忆化的过程 简化运算
*/

#include <bits/stdc++.h>
using namespace std;

int H[6006];
int dp[6006][2]; // 0: 不选, 1: 选
map<int, vector<int>> mp; // 邻接表表示树
int tre[6006]; // tre[i] 表示节点 i 的父亲

// DFS 函数计算最大开心值
int dfs(int x, int p) {
    if (dp[x][p] != -1) {
        return dp[x][p];
    }

    if (p == 1) { // 如果选了当前节点
        int mx = 0;
        for (auto i : mp[x]) {
            mx += dfs(i, 0); // 孩子不能选
        }
        dp[x][1] = H[x] + mx;
    } else { // 如果没选当前节点
        int sum = 0;
        for (auto i : mp[x]) {
            sum += max(dfs(i, 0), dfs(i, 1)); // 孩子可以选也可以不选
        }
        dp[x][0] = sum;
    }

    return dp[x][p];
}

int main() {
    int N;
    cin >> N;

    for (int i = 1; i <= N; ++i) {
        cin >> H[i]; // 输入开心值
    }

    fill(tre, tre + N + 1, 0);
    for (int i = 1; i < N; ++i) {
        int l, k;
        cin >> l >> k;
        mp[k].push_back(l); // 加入所有孩子
        tre[l] = k; // 指向父亲
    }

    // 找到根节点
    int p = 1;
    while (tre[p] != 0) {
        p = tre[p];
    }

    // 初始化 dp 数组为 -1 表示未计算状态
    memset(dp, -1, sizeof(dp));

    // 计算最大开心值
    int result = max(dfs(p, 0), dfs(p, 1));

    cout << result << endl;

    return 0;
}

石子合并

题目要求给你一堆石子,只能合并彼此相邻的,合并所需要花费的代价为两者之和,求合成一堆,所需最少的代价

利用前缀和快速求出来区间内和,每次合并相当于分成两堆,先把这两堆合并了,然后堆里面再合并小的堆.

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int num[N];
int pre[N];
int dp[N][N];

// 给一个左右边界
int dfs(int a,int b)
{
    // 如果相等 就说明不需要合并 结果就为0
    if(dp[a][b]!=-1) return dp[a][b];
    if(a==b) return 0;

    int mn = 1e8;
    // 这代表的含义是将这两堆放在一起
    for(int i = a;i<b;i++)
    {
        mn = min(dfs(a,i)+dfs(i+1,b)+pre[b]-pre[a-1],mn);
    }
    // 得出一个结论 不要轻易在循环里面更新dp值
    dp[a][b] = mn;
    return dp[a][b];
}
int main()
{
    int N;cin >> N;
    // 是不是有点类似归并排序 当成一组来处理
    //彼此合并 寻找最小合并值 这咋用dp做
    // 记忆化搜索加上前缀和 dp[i][j] 代表i到j的区间最小代价
    // dp[i][j] = min{dp[i][k]+dp[k][j]+v[i~j], dp[i][j]}
    for(int i = 1;i<=N;i++)
    {
        int x;cin >> num[i];
        pre[i] = num[i] + pre[i-1];
    }
    memset(dp,-1,sizeof (dp));
    cout << dfs(1,N);

    return 0;
}