Maximum Path Sum in Triangle with Equal Odd and Even Integers

user_15476924 0
Viewed 168

I was given an algorithm task to find the maximum path sum in a triangle (containing only positive integers) where the path passes through an equal number of even and odd integers, starting from the top element. The path could either go downwards or bottom right. For instance:

5
6 7
11 13 5
2 21 14 3
8 9 20 22 23

Would return a result of 5+6+13+14=38. It would not consider the last row as that would only result in an imbalanced number of odd and even integers.

I am aware of the method used to find the standard maximum path sum in a triangle, using dynamic programming in a bottom to top approach. However, I do not know how to approach this problem as there seem to be too many possibilities to reduce it down in a similar fashion.

I tried under the assumption that every two rows should have an even and odd integer, however that does not account for all possible solutions under these restrictions as the path could be [odd, odd, odd, even, even, even] or something similar. Just an idea of a recurrence or relation I could use to solve this would be very much appreciated.

graph-algorithm algorithm
1 Answers

First some points can be inferred from problem statement,

  1. If the size of triangle is odd, we neglect the last row as for number of odd integers = number of even integers the path length should be even.
  2. The number of odd/even numbers in any path from top to bottom can be at maximum n.

In the standard maximum path sum in a triangle the recurrence is given by,

Dp[i][j] = max(Dp[i + 1][j], Dp[i + 1][j + 1]) + currentElement

So for this problem to account for equal odd and even numbers, we need to keep track of the path parity (the number of odd and even numbers) in each dp state. This means the recurrence will become,

Dp[i][j][k] = max(Dp[i + 1][j][k - parity], Dp[i + 1][j + 1][k - parity]) + currentElement,

where parity is current element parity, +1 for even and -1 for odd.
Answer is given by Dp[0][0][number of rows]
Here (link) is the solution using bottom up dynamic programming in C++.

user_99289080
Related