Looking for hints to solve this dynamic programming problem

Here is the idea.

At each point in the singing, the current state can be represented by who the singers are, how long they have been singing, and which ones are currently out of breath. And from each state we need to transition to a new state, which is every singer out of breath is ready to sing again, every singer singing is good for one less turn, and new singers might be chosen.

Done naively, there are up to 20 choose 3 singers, each of which can be in 10 current states, plus up to 2 more who are out of breath. This is 175560000 combined states you can be in. That's too many, we need to be more clever to make this work.

Being more clever, we do not have 20 differentiable singers. We have 10 buckets of singers based on how long they can sing for. If a singer can sing for 7 turns, they can't be in 10 states if currently singing, but only 7. We do not care whether the two can sing for 7 turns are at 4 and 3 turns left or 3 and 4, they are the same. This introduces a lot of symmetries. Once we take care of all of the symmetries, that reduces the number of possible states that we might be in from hundreds of millions to (usually) tens of thousands.

And now we have a state transition for our DP which is dp[state1] to dp[state2]. The challenge being to produce a state representation that takes advantage of these symmetries that you can use as keys to your data structure.

UPDATE:

The main loop of the code would look like this Python:

while not finished:
    song_length += 1
    next_states = set()
    for state in current_states:
        for next_state in transitions(state):
            if is_finished(next_state):
                finished = True # Could break out of loops here
            else:
                next_states.add(next_state)
    current_states = next_states

Most of the challenge is a good representation of a state, and your transitions function.

The state in terms of memoisation seems unrelated to the time elapsed since the start. Take any starting position,

a, b, c

where a, b, c are chosen magnitudes (how long each singer can hold their breath), and a is the smallest magnitude. We have

a, b, c
t = 0

and it's the same as:

0, b - a, c - a
t = a

So let's define the initial state with smallest magnitude a as:

b, c, ba, ca
  where ba = b - a
        ca = c - a
t = a

From here, every transition of the state is similar:

new_a <- x
  where x is a magnitude in
  the list that can be available
  together with b and c. (We only
  need to try each such unique
  magnitude once during this
  iteration. We must also prevent
  a singer from repeating.)

  let m = min(new_a, ba, ca)

  then the new state is:
    u, v, um, vm
    t = t + m
      where u and v are from the
      elements of [new_a, b, c] that
      aren't associated with m, and um
      and vm are their pairs from
      [new_a, ba, ca] that aren't m,
      subtracted by m.

The state for memoisation of visited combinations can be only:

[(b, ba), (c, ca)] sorted by
the tuples' first element

with which we can prune a branch in the search if the associated t that is reached is equal or higher to the minimal one seen for that state.

Example:

2 4 7 6 5

Solution (read top-down):

4 5 6
7 4 5
  2

States:

u v um vm
5 6 1 2
t = 4

new_a = 7
m = min(7, 1, 2) = 1 (associated with 5)
7 6 6 1
t = 5

new_a = 4
m = min(4, 6, 1) = 1 (associated with 6)
4 7 3 5
t = 6

new_a = 5
m = min(5, 3, 5) = 3 (associated with 4)
5 7 2 2
t = 9

new_a = 2
m = min(2, 2, 2) = 2 (associated with 2)
5 7 0 0
t = 11

Python code:

import heapq
from itertools import combinations

def f(A):
  mag_counts = {}

  for x in A:
    if x in mag_counts:
      mag_counts[x] = mag_counts[x] + 1
    else:
      mag_counts[x] = 1

  q = []

  seen = set()

  # Initialise the queue with unique starting combinations
  for comb in combinations(A, 3):
    sorted_comb = tuple(sorted(comb))
    if not sorted_comb in seen:
      (a, b, c) = sorted_comb
      heapq.heappush(q, (a, (b-a, b), (c-a, c), a))
    seen.add(sorted_comb)

  while q:
    (t, (ba, b), (ca, c), prev) = heapq.heappop(q)

    if ba == 0 and ca == 0:
      return t

    for mag in mag_counts.keys():
      # Check that the magnitude is available
      # and the same singer is not repeating.
      [three, two] = [3, 2] if mag != prev else [4, 3]
      if mag == b == c and mag_counts[mag] < three:
        continue
      elif mag == b and mag_counts[mag] < two:
        continue
      elif mag == c and mag_counts[mag] < two:
        continue
      elif mag == prev and mag_counts[mag] < 2:
        continue

      m = min(mag, ba, ca)

      if m == mag:
        heapq.heappush(q, (t + m, (ba-m, b), (ca-m, c), m))
      elif m == ba:
        heapq.heappush(q, (t + m, (mag-m, mag), (ca-m, c), b))
      else:
        heapq.heappush(q, (t + m, (mag-m, mag), (ba-m, b), c))

  return float('inf')

As = [
  [3, 2, 3, 3], # 3
  [1, 2, 3, 2, 4], # 3
  [2, 4, 7, 6, 5] # 11
]

for A in As:
  print A, f(A)