本文主要是介绍DP-数塔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：从塔顶到塔底，每个点都有一个数字，求一条不能回走的路径，使经过的点的和最大
题目链接：数塔
解题思路：咳咳，题目都说了是个DP题，那就用DP方法吧！DP有自顶向下和自顶向上两种方法，可以试着比较两种方法。
自底向上的状态转移方程dp[i][j]=a[i][j]
=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
自顶向下的就不多说了，都差不多，但比自顶向下要单独考虑每层最后一个和第一个的情况。
代码：
#include#include#include#includeusing namespace std;
int dp[105][105],a[105][105];
int main()
{
int T,i,j,n;
cin>>T;
while(T--){
cin>>n;
memset(dp,0,sizeof(dp));
for(i=0;i>a[i][j]; if(i== n-1) dp[i][j]=a[i][j]; //自底向上 } } for(i=n-2;i>=0;i--){ for(j=0;j #include #include #include using namespace std; int dp[105][105],a[105][105]; int main() { int T,i,j,n,ans; cin>>T; while(T--){ cin>>n; memset(dp,0,sizeof(dp)); for(i=0;i >a[i][j]; } } dp[0][0]=a[0][0]; //自顶向下 for(i=1;i 这篇关于DP-数塔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
