One Pass 1258 - Digital Pyramid (Dynamic Programming)

Title

Original title linkhttp://ybt.ssoier.cn:8088/problem_show.php?pid=1258[Title Description]

Observe the digital pyramid below.Write a program to find a path that ends anywhere from the highest point to the bottom, so that the sum of the paths passing through the numbers is the largest.Each step can go from the current point to the lower left point or to the lower right point.

In the example above, the path from 13 to 8 to 26 to 15 to 24 yields the largest sum of 86.

[Enter]

The first line contains R (1≤R≤1000), indicating the number of lines.

Each subsequent row contains an integer that is contained in a particular row of this digital pyramid.

All integers supplied are non-negative and not greater than 100.

[Output]

A single line containing the largest possible sum.

[Sample input]

51311 812 7 266 14 15 812 7 13 24 11

[Example output]

86

Thoughts

This problem needs to be done with dynamic programming, not greedy

You can choose the largest of the two branches below each time.This can be done with the help of depth-first search.

Directly using depth-first search will time out, so you need to add memoization

Steps

1. Define variables

const int N=1010;int a[N][N],mk[N][N];int n;

2. Define the deep search function

int dfs(int x,int y){if(x>n) return 0;if(mk[x][y]!=-1) return mk[x][y];return mk[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];}

3. Main program

int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}memset(mk,-1,sizeof(mk));cout<

Complete code

#includeusing namespace std;const int N=1010;int a[N][N],mk[N][N];int n;int dfs(int x,int y){if(x>n) return 0;if(mk[x][y]!=-1) return mk[x][y];return mk[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+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];}}memset(mk,-1,sizeof(mk));cout<

Novice, please give me more advice