faryou的技术折腾 - 2024年8月
type: channel
link: https://blog.faryou.eu.org/tech/index.php/2024/08/
description: 原谅我这一生不羁放纵爱自由~
items: 【算法教程】【C/C++】DP（动态规划）：背包DP——程序设计思路与代码实现
items: 【算法教程】【C/C++】DP（动态规划）：简单动规问题——程序设计思路与代码实现

【算法教程】【C/C++】DP（动态规划）：背包DP——程序设计思路与代码实现
type: item
date: 2024-08-19T19:50:00+08:00
description: 前言上一篇文章中我们学习了简单DP，今天我们来学习一种也很常见的DP——背包DP。程序设计思路背包DP以01背包和完全背包为基础，其他的背包DP都由这两种延伸出去，先看01背包：01背包是最简单的背包DP，它是指有n样物品，第i样物品的价值为xi，所占用的容量为yi，你有一个容量为m的背包，要求你用这个背包装下价值最高的物品，每种物品只能装一次。这里每样物品的状态都只有装或不装。故我们可以列出状态转移方程：fi=max(fi-1,fi-1+xi（fi表示在第1到第i个物品中选容量为j的物品能获得的最多的价值）。完全背包与01背包的区别在于它每样物品可以选无数次，但它的状态转移方程和01背包有不同。我们可以列出状态转移方程：fi=max(fi-1+k*xi)（这里的k是指购买了k件i物品，是for循环中的变量），这样做的时间复杂度为O(n3)，明显偏慢了。但是我们还有下面的优化：fi=max(fi-1,fi+xi)，因为我们在进行这次转移前就已经充分的考虑了。这个优化必须自己想清楚。代码实现来看一个01背包问题：很明显，这是一道背包题。直接看代码：#include <bits/stdc++.h> int n,m,a[105],dp[105][1005];//n、m、a如题意，dp指上文中i int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){//分类讨论，判断能不能买 if(j==a[i]) dp[i][j]=dp[i-1][j]+1; if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]; if(j<a[i]) dp[i][j]=dp[i-1][j]; } printf("%d",dp[n][m]); return 0; }DP注重的是自己的理解，而且讲解无法达到很好的效果，请自行理解源码~结语背包问题是DP中较为简单的一类，要想学好DP，就应该多刷题，以此总结经验。我是faryou，再见！

【算法教程】【C/C++】DP（动态规划）：简单动规问题——程序设计思路与代码实现
type: item
date: 2024-08-10T18:21:00+08:00
description: 前言上一篇文章中介绍了递推，其实也是为今天的DP打好基础。程序设计思路DP本质上就是对题目进行分类讨论，列出其不同情况下的状态转移方程，然后套上循环求解。DP的种类有很多，其应用范围几乎涵盖了全部的算法内容，理论上来说，只要你有能力列出状态转移方程，DP可以解决几乎一切问题。今天我们讲一下简单的DP，了解一下DP的思路。代码实现由于DP的可拓展性太强，今天我破例用两道题进行讲解：这道题要求我们得到最大的和。这里有一个思路：每次将金字塔底部相邻的两个数相比较，将大者加到这两个数正上方的数上。即：fx=max(fx,fx+1)+fx（金字塔存储为直角三角形）。下面是代码：#include <bits/stdc++.h> int r,f[1005][1005];//r如题意，f为DP用数组 int main(){ scanf("%d",&r); for(int i=0;i<r;i++) for(int j=0;j<i+1;j++) scanf("%d",&f[i][j]);//读入数据 for(int i=r-1;i>0;i--) for(int j=0;j<r-1;j++) f[i-1][j]+=max(f[i][j],f[i][j+1]);//递推式 printf("%d",f[0][0]);//输出塔尖 return 0; }这道题是经典动规题，我们通过层层上推求出结果。再来看下面这题：本题初看没有思路，但是细细一想，一个长度为n的上升子序列可以分为前面长度为n-1的上升子序列和后面的一个数，那么我们可以先把所有f[x]都初始化为1，之后用双层循环（双指针），将后面的大数和前面的子序列拼为一个序列。由此，我们可以列出这样的方程：f[x]=max(f[i],f[j-1])（f[x]表示从第1到第x个数的最长上升子序列长度），下面是代码：#include <bits/stdc++.h> int n,ans=0,a[5005]={0},f[5005]={0}; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); f[i]=1; }//以上为读入+初始化（一个数自己也算最长上升子序列） for(int i=1;i<=n;i++) for(int j=1;j<=i-1;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);//递推式，当找到一个更大的数时，将其加入前面的子序列 for(int i=1;i<=n;i++) ans=max(ans,f[i]);//拿到最长长度 printf("%d",ans);//输出 return 0; }结语其实DP本身的思路不难，关键在于你能不能找出所有情况。下篇文章，我将介绍背包DP。我是faryou，再见！