Algorytmy i struktury danych · Middle · Pytanie 75 z 75
Subset sum: czy niektóre z liczb sumują się do target? Jakie jest klasyczne rozwiązanie DP?
- 1Posortować liczby i zachłannie brać największe, które jeszcze się mieszczą
- 2Sprawdzić wszystkie permutacje liczb i ich sumy
- ✓Poprawna odpowiedź: Tablica logiczna osiągalnych sum aktualizowana dla każdej liczby: O(n × target)
Wyjaśnienie
reachable[s] mówi, czy da się uzyskać sumę s; dla każdej liczby aktualizujemy sumy od największych do najmniejszych, aby użyć jej raz. Podejście zachłanne może przegapić rozwiązanie, a permutacje to O(n!). DP jest pseudowielomianowe: szybkie, dopóki target jest mały.