Python

The DP solution to go column by column and compute the min flaps for each cell is correct but too slow. Fortunately this problem can be solved using MATH

# Uses math to calculate the minimum number of flaps needed to reach the last passage at any height.
# This solution relies on a couple of facts:
#   1. The number of flaps needed to reach a passage at (x, y) is ceil((x + y) / 2).
#       Proof:
#       - Each flap increases your height by 1 and each glide decreases it by 1
#       - Suppose you flapped f times and covered a horizontal distance of x
#       - So your final height would be y = f - (x - f) = 2f - x
#       - Now suppose a passage at position p_x begins at height p_y. To enter it, your height must be, y >= p_y
#       - Substituting y, 2f - x >= p_y => 2f - p_x >= p_y
#       - Solving for f, f >= (p_x + p_y) / 2
#       - Since f is an integer, f = ceil((p_x + p_y) / 2)
#   2. For each wall, the lowest opening gives the smallest lower bound on the cumulative number of flaps.
#      The maximum of these bounds is necessary because an earlier high wall may require more flaps than the last wall.
#   3. For this input, that maximum lower bound is attainable through all the walls, so it is the optimal answer.
#      This is not true in general: an opening's upper edge or the distance between walls can make the lowest opening unreachable.
def flapsMath(data: str):
    flaps = 0

    passages = [[int(p) for p in passage.split(',')] for passage in data.splitlines()]
    passages.sort(key=lambda p: (p[0], p[1]))  # Sort passages so that we always have the lowest opening first
    last_seen_x = 0

    for x, y, _ in passages:
        if x != last_seen_x:
            last_seen_x = x
            # calculate the minimum number of flaps needed to cross this passage at its lowest opening
            # (x + y + 1) // 2 is equivalent to ceil((x + y) / 2) for integers
            flaps = max(flaps, (x + y + 1) // 2)

    return flaps