动归基本题目四种方法

原题链接：627.数字三角形

深搜邈和广搜邈

2025-01-14 11:09:43

发布于：上海

2阅读

0回复

0点赞

方法一：顺推法

根据题意，可以得出转移方程式：

$dp[i][j]=\max(dp[i-1][j-1],dp[i-1][j])+a[i][j]$

如果把 $a[i][j]$ 忽略，改成变量 $k$ ，也不会有什么大碍。因此，可以写出下列代码：

#include<iostream>
using namespace std;
#define int long long
int dp[101][101],k,n,ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>k;
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+k;
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

方法二：一维顺推

这道题目出题人很善良，所谓的行数 $r$ 满足要求：

$1\leq r\leq100$

当然，如果所谓的行数 $r$ 过大超过大约 $3000$ 的话，由于状态转移方程式中只涉及到 $dp[i-1][j]$ 和 $dp[i-1][j-1]$ 两者，可以考虑只开一维数组（当然也可以开滚动数组），代替二维。
状态转移方程式变为了：

$dp[j]=\max(dp[j-1],dp[j])+k$

唯一的麻烦就是如果从左往右存储会发生当 $m=j+1$ 时， $dp[j]$ 发生改变后 $dp[m]=max(dp[m-1],dp[m])+k$ 这里 $dp[m-1]$ 已经是更新过后的值了，不符合题意。因此，必须从右往左存储。

#include<iostream>
using namespace std;
#define int long long
int dp[101],k,n,ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=i;j;j--){
			cin>>k;
			dp[j]=max(dp[j],dp[j-1])+k;
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

方法三：逆推法

顺推法有优点也有缺点。优点是方法简单容易想到，而且可以优化空间省去数组 $a[101][101]$ 。
但是缺点是它有多个终点，直接输出 $dp[n][n]$ 明显不是最大值，必须遍历一遍获得最大值输出。
因此，我们可以考虑设置多个起点出发回到同一个终点。这就是逆推法主要思想。
状态转移方程式：

$dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]$

当然，这里需要先输入所有的 $a[i][j]$ ，再进行逆推过程，不能省去 $a[101][101]$ 这个二维数组。

#include<iostream>
using namespace std;
#define int long long
int dp[101][101],a[101][101],n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=n;i;i--)dp[n][i]=a[n][i];
	for(int i=n-1;i;i--){
		for(int j=1;j<=i;j++){
			dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
		}
	}
	cout<<dp[1][1];
	return 0;
}

方法四：一维逆推

和顺推法一样，逆推法的 $dp[101][101]$ 是二维数组，当所谓的行数 $r$ 超过大约 $3000$ 时，空间就会不够。因此，我们考虑逆推法的一维状态转移方程式。
由逆推法知道， $dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]$ ， $dp[i][j]$ 只取决于 $dp[i+1][j]$ 和 $dp[i+1][j+1]$ ，因此降维操作不影响结果，则状态转移方程式变为：

$dp[j]=\max(dp[j],dp[j+1])+a[i][j]$

令 $m=j+1$ ，则先推完 $dp[j]$ ，取决于 $dp[j]$ 和 $dp[m]$ ，而 $dp[m]$ 这一轮还没有推；再推 $dp[m]$ ，涉及到 $dp[m]$ 和 $dp[m+1]$ ，没涉及到 $dp[j]$ 。因此，逆推法用一维数组实现，循环不用从后往前，直接从前往后推即可。

#include<iostream>
using namespace std;
#define int long long
int dp[101],a[101][101],n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=n;i;i--){
		for(int j=1;j<=i;j++){
			dp[j]=a[i][j]+max(dp[j],dp[j+1]);
		}
	}
	cout<<dp[1];
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

方法一：顺推法

方法二：一维顺推

方法三：逆推法

方法四：一维逆推

热门讨论