四、记忆化搜索
题目链接：901. 滑雪
4.1题目描述
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
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
在给定矩阵中，一条可行的滑行轨迹为24−17−2−1。
在给定矩阵中，最长的滑行轨迹为25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300,0≤矩阵中整数≤10000
输入样例：
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
4.2思路分析
1）状态表示
集合：所有从 (i,j) 开始滑的路径。
属性：f[i][j]表示满足条件集合中的滑行距离的最大值。
2）状态计算
集合划分：按照从当前位置开始第一步是从上、下、左、右哪个方向开始滑行的进行分类。
计算：针对每一种状态，假设第一步走到的点是(x,y)，则我们在计算f[i][j]时可以先将从(i,j)到(x,y)的距离去掉，则就变成了求从(x,y)开始滑行，可以滑行的最大距离。按照集合定义我们可知即为f[x][y]。所以，可得转移方程为 f[i][j]=max(f[i][j],f[x][y]+1)。而每一次的f[][]我们需要用dfs来求，所以我们用dfs+记忆化搜索，也相当于是dp来进行求解了。
4.3代码实现
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N=310; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; //方向数组，存储四个方向的偏移量 int f[N][N]; int h[N][N]; int r,c; //dp(x,y)返回从(x,y)开始滑行，可以滑行的最大距离 int dp(int x,int y){ if(f[x][y]!=-1) return f[x][y]; //如果当前状态已经被计算过，直接返回即可 f[x][y]=1; //否则，当前的状态的滑行距离至少为1（当前位置） //枚举上、下、左、右四个方向 for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; //如果该方向的点在范围内，而且可以滑过去 if(a>=1&&a<=r&&b>=1&&b<=c&&h[a][b]<h[x][y]) f[x][y]=max(f[x][y],dp(a,b)+1); //转移方程 } return f[x][y]; } int main(){ cin>>r>>c; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ cin>>h[i][j]; } } memset(f,-1,sizeof f); //将每种状态初始化为-1 int res=1; //枚举每个点，求出从每个点开始滑行的最大距离，然后再在其中取一个最大值即为答案 for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ res=max(res,dp(i,j)); } } cout<<res; return 0; }
五、树形DP
题目链接：285. 没有上司的舞会
5.1题目描述
Ural 大学有 N 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数 N。
接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。
输出格式
输出最大的快乐指数。
数据范围
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
输出样例：
5
5.2思路分析
1）状态表示
集合：f[u][0]表示所有从以u为根的子树中选择，并且不选择u这个点的方案。f[u][1]表示所有从以u为根节点的子树中选，并且选择u这个点的方案。
属性：所有人快乐指数总和的最大值。
2）状态计算
集合划分：分为f[u][0]和f[u][1]。
计算：设u的每个子树的根节点为si。每次递归地对子树进行下述处理。针对f[u][0]由于不选择u这个根结点，所以每次累加的时候可以依据选上子树根节点后值的变化来选，如果选上子树根节点总值大，则就加上该条路径，否则就加上不选子树根节点的这条路径即f[u][0]+=max(f[si][0],f[si][1])；针对f[u][1]由于选了u这个根节点，所以每次不能选包含子树根结点的路径，所以f[u][1]+=f[si][0]。
5.3代码实现
#include <iostream> #include <cstring> using namespace std; const int N=6010; int happy[N]; int h[N],e[N],ne[N],idx; //邻接表存储树 int f[N][2]; bool has_father[N]; //记录每个点是否有父结点，便于后续找到根节点 int 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]; //f[u][1]因为一定选u这个点，所以其初始值为结点u的快乐值 //枚举u的每条边 for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; dfs(j); //递归求解 f[u][0]+=max(f[j][0],f[j][1]); //转移方程 f[u][1]+=f[j][0]; //转移方程 } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>happy[i]; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++){ int l,k; cin>>l>>k; has_father[l]=k; add(k,l); } int root=1; while(has_father[root]) root++; //寻找根节点 dfs(root); cout<<max(f[root][0],f[root][1]); return 0; }
