10819 - Trouble of 13-Dots

DP, programación dinámica, dynamic programming.

Es parecido al problema de la mochila (Knapsack 0/1 problem).

El estado que utilice:

dp[i][j] = Utilizando un subconjunto de los elementos [0..i],
el máximo valor que puedo comprar gastando exactamente j pesos.

dp[i][j] == INT_MIN si no puedo escoger un subconjunto de los
elementos [0..i] que valga exactamente j pesos.