dp
数字三角形(POJ1163)
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为0 -99
//递归式
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j){
if(i==n)
return D[i][j];
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
return max(x,y)+D[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
cout << MaxSum(1,1) << endl;
}
//带记忆化储存递归式
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int dp[100][100];
int num[100][1000];
int n;
int max_num(int i,int j)
{
if(dp[i][j]!=-1)return dp[i][j];
if(i==n)dp[i][j]=num[i][j];
else
{
int x=max_num(i+1,j);
int y=max_num(i+1,j+1);
dp[i][j]=max(x,y)+num[i][j];
}
return dp[i][j];
}
int main()
{
int i,j,k;
int x,y;
memset(dp,0,sizeof(dp));
cin>>n;
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
{
cin>>num[i][j];
dp[i][j]=-1;
}
cout<<max_num(1,1)<<'
';
// for(i=1; i<=n; i++){
// for(j=1; j<=i; j++)
// {
// printf("%d ",dp[i][j]);
// }
// puts("");
// }
return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/
递推式
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int dp[100][100];
int num[100][100];
int n;
void max_num()
{
int i,j;
for(i=1; i<=n; i++)//初始化最后一排，从最后一排向第一排推
dp[n][i]=num[n][i];
for(i=n-1; i>=1; i--)
{
for(j=1; j<=i; j++)
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+num[i][j];
}
}
int main()
{
int i,j,k;
int x,y;
memset(dp,0,sizeof(dp));
cin>>n;
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
{
cin>>num[i][j];
}
max_num();
cout<<dp[1][1]<<'
';
// for(i=1; i<=n; i++){
// for(j=1; j<=i; j++)
// {
// printf("%d ",dp[i][j]);
// }
// puts("");
// }
return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/
空间优化后用一维数组维护（其实可以更加简单直接在保存原始数据的数组里直接更新，这样就不需要额外的空间）
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int dp[100];
int num[100][100];
int n;
void max_num()
{
int i,j;
for(i=1; i<=n; i++)
dp[i]=num[n][i];
for(i=n-1; i>=1; i--)
{
for(j=1; j<=i; j++)
dp[j]=max(dp[j],dp[j+1])+num[i][j];
}
}
int main()
{
int i,j,k;
int x,y;
memset(dp,0,sizeof(dp));
cin>>n;
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
{
cin>>num[i][j];
}
max_num();
for(i=1;i<=n;i++)printf("%d ",dp[i]);
puts("");
cout<<dp[1]<<'
';
return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/