Shulou(Shulou.com)06/02 Report--

Editor to share with you how to achieve the digital triangle, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

The problem with digital triangles. There is a triangle made up of nonnegative numbers, as shown in the figure.

Starting from the first line, you can go down to the left or down to the right one at a time until you reach the bottom line and add up all the numbers you have passed along the way. how can you make this sum maximum?

Our most conventional idea is to use backtracking to traverse each path and then choose the longest path.

A more efficient algorithm for this problem is dynamic programming. If the current position (iMagnej) is regarded as a state, and then the index function d (iMagnej) is defined as the maximum sum that can be obtained from the lattice (iMagnej) (including the sublattice itself), then this problem is transformed into finding d (1jue 1).

In the topic of dynamic programming, the state transition equation is undoubtedly very important. Let's take a look at the state transition equation d (iMaginj) = a (iMaginj) + max {d (ifujj), where a (iMagnej) represents the number of each circle.

Here is the code

# include#includeusing namespace std;int value [4] [4]; int dp [4] [4]; int main () {for (int itimo [I] [j]);} for (int itimo / for -) for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.