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)<<'\n'; // 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]<<'\n'; // 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]<<'\n'; return 0; } /* 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 */
