DP (Dynamic Programming) math problem

On Brilliant.org there's a problem that has a solution that uses DP.
https://brilliant.org/problems/bean-coloring/

Proven Inequalities Reference

• x2≥0
• a2+b2≥2ab
• (a−b)2≥0
• a2+b2+c2≥ab+bc+ca
• (a+b)/2≥ ab−−√
• https://brilliant.org/wiki/titus-lemma/
• https://artofproblemsolving.com/wiki/index.php?title=Root-Mean_Square-Arithmetic_Mean-Geometric_Mean-Harmonic_mean_Inequality

1+1+2+1+2+3+1+2+3+4...

Why does
1+1+2+1+2+3+1+2+3+4...n
turn into
n*(n+1)/2?

1 = 1





1+2 = 3





1+2+3 = 6

^ Solving for n = 3, we need to calculate the number of dots in the triangle right above this sentence.

To get this triangle, we first need to make a square. This square below is n x (n+1), or 3 x 4.

This triangle has an area of 3 * 4 or 12. It also contains two "1+2+3" triangles.

Dividing this square by two gets the triangle that equals 6, which is a 1+2+3 triangle.

With n = 4, you do the same thing.

When you divide this 5 x 4 square by 2, you get a "1+2+3+4" triangle.

Therefore, n*(n+1) is the square which is made up of two triangles that have a sum of 1+2+...n, and when you divide it by two, you get one triangle with the sum from 1 -> n.