Euler project #18 approach

by

It’s something called dynamic programming.

You have such triangle:

   3
  7 4
 2 4 6  
8 5 9 3

When you move from the bottom to the top, you can calculate the best choices on last iteration.
In this case you take the last row 8 5 9 3 and maximize sum in addition to previous line.

Iteration 1:
Assume that you are on last-1 step.

You have line 2 4 6, let’s iterate on it.

From 2, you can go to either 8 or 5, so 8 is better (maximize your result from 2) so you calculate first sum 8 + 2 = 10.

From 4, you can go to either 5 or 9, so 9 is better (maximize your result from 4) so you calculate second sum 9 + 4 = 13.

From 6, you can go to either 9 or 3, so 9 is better again (maximize your result from 6) so you calculate third sum 9 + 6 = 15.

This is the end of first iteration and you got the line of sums 10 13 15.

Now you’ve got triangle of lower dimension:

    3
  7  4
10 13 15

Now go on until you get one value, which is exactly 23.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Find a pair of elements from an array whose sum equals a given number
  3. The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
  4. How do you calculate the average of a set of circular data? [closed]
  5. circle-circle collision
  6. Algorithm to check similarity of colors
  7. Finding maximum for every window of size k in an array
  8. Generate all unique substrings for given string
  9. Non-recursive depth first search algorithm [closed]
  10. How to Compute OBB of Multiple Curves?
  11. Calculating new longitude, latitude from old + n meters
  12. How do you validate a binary search tree?
  13. Floating Point Divider Hardware Implementation Details
  14. Best algorithm to test if a linked list has a cycle
  15. How to check if line segment intersects a rectangle?
  16. How to compare two shapes?
  17. Draw Quadratic Curve on GPU
  18. Probability of collision when using a 32 bit hash
  19. What string similarity algorithms are there?
  20. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  21. Obfuscating an ID
  22. Algorithm for autocomplete?
  23. An inverse Fibonacci algorithm?
  24. What algorithm can calculate the power set of a given set?
  25. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  26. How do I find the median of numbers in linear time using heaps?
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  28. Finding rectangles in a 2d block grid
  29. Check if array B is a permutation of A
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment