乌丑 @ 2021-12-12 20:12:14
老师让我们用dfs，又把最大路径和改成最小路径和，于是我给出了如下代码
#include<bits/stdc++.h>
using namespace std;
int a[100][100],n;
int dfs(int x,int y) {
if(x==n) return a[x][y];
int left=dfs(x+1,y),right=dfs(x+1,y+1);
return min(left,right)+a[x][y];
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) cin>>a[i][j];
cout<<dfs(1,1);
return 0;
}但是老师考虑到会有大量多次计算，让我剪枝，然后就不会了，
比如：
红色圈中的数在left中被算了一次，在right中又被算了一次，如何避免？？
by Y2y7m @ 2021-12-12 20:16:10
非要用搜索吗，动规他不香吗？
by 45dino @ 2021-12-14 21:55:03
@乌丑 可以考虑记忆化
对于每个点存储一个值，表示前面到这个点经过的数的总和的最小值。
假如某一次dfs又到达了这个点，就先拿这个值与本次dfs的和进行比较，假如存下来的这个值更小，就没有必要继续下去。
by newbie_QwQ @ 2021-12-14 21:55:56
使用记忆化搜索。
#include<iostream>
using namespace std;
int bs[1001][1001],zd[1001][1001];
int dfs(int x,int y,int n)
{
if(x==n) return bs[x][y];
if(zd[x][y]!=-1) return zd[x][y];
return zd[x][y]=max(dfs(x+1,y,n),dfs(x+1,y+1,n))+bs[x][y];
}
int main()
{
int i,j,n;
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
cin>>bs[i][j];
zd[i][j]=-1;
}
}
cout<<dfs(1,1,n);
return 0;
}by newbie_QwQ @ 2021-12-14 21:56:38
拿空间换时间就可以了。
by tobie @ 2021-12-14 21:59:36
@乌丑
您可以设置一个数组f[x][y]，初始值设为-1。
搜索时如果f[x][y]==-1 则没有被遍历过按照正常流程走，同时用算出的答案去更新f[x][y]（告诉程序dfs(x,y)已经算过了，下一次遇到后可以直接返回f[x][y]中存的数）;
如果f[x][y]!=-1，则说明dfs(x,y)已经被算过了，直接返回f[x][y]即可。
int a[100][100],n;
int dp[100][100];
int dfs(int x,int y) {
if(dp[x][y]!=-1) return dp[x][y];
if(x==n) return a[x][y];
int left=dfs(x+1,y),right=dfs(x+1,y+1);
return dp[x][y]=min(left,right)+a[x][y];
}