Din enunţ intuim că o componentă a stării trebuie să fie submulţimea participanţilor aflaţi în plută în punctul curent, intuiţie confirmată de numărul mic al participanţilor ({$N ≤ 10$}). Există $2^10^$ astfel de variante, din care vom exclude varianta în care pluta este goală. O stare a problemei, reprezentănd soluţia unei subprobleme, va fi alcătuită din poziţia curentă a plutei (punctul $P{~i~}$ unde se află) şi submulţimea oamenilor care se află în plută. Observăm că de la punctul precedent au coborât nişte oameni, au urcat alţii apoi pluta a continuat spre punctul curent; aceşti paşi contribuie la timpul total şi reprezintă 2 părţi ale recurenţei soluţiei. Dacă notăm cu $T{~m~}[i][S]$ timpul minim necesar pentru a ajunge în punctul $i$ cu submulţimea $S$ a oamenilor din plută, putem descrie problema prin relaţiile:
<tex> $T_m[0][0] = 0$ </tex>

<tex> $T_m[0][S] = \infty, \forall S \neq 0$ </tex>
<tex> $T_m[i][0] = \infty, \forall 1 \le i \le M$ </tex>
<tex> $T_m[i][S] = \min_{S'} \{T_m[i-1][S'] + T_u[S'][S] + T_c[S'][S] + T_t[i][S] \}, \forall 1 \le i \le M, \forall S \neq 0$ </tex>

<tex> $T_m[0][S] = T_u[0][S], \forall S \neq 0$ </tex>
<tex> $T_m[i][S] = \min_{S'} \{T_t[i][S'] + T_m[i-1][S'] + T_u[S'][S] + T_c[S'][S]\}, \forall 1 \le i \le M$ </tex>

unde $T{~u~}[S'][S]$ este timpul necesar pentru urcarea participanţilor care se găsesc în mulţimea $S$ dar nu fac parte din mulţimea $S'$ (aceşti participanţi alcătuiesc mulţimea $S{~u~}$), $T{~c~}[S'][S]$ este timpul necesar pentru coborârea participanţilor din plută (participanţii din mulţimea $S{~c~}$), iar $T{~t~}[i][S]$ este timpul necesar traversării curentului de la punctul $i-1$ la punctul $i$ dacă în plută se află participanţii din $S$. Formulele pentru valorile $T{~u~}$, $T{~c~}$ şi $T{~t~}$ sunt:

În formula pentru $T{~m~}[i][S]$, observăm că $T{~t~}[i][S]$ nu depinde de argumentul funcţiei de minimizare, adică de starea iniţială, deci putem scoate valoarea în afara funcţiei. Valoarea pe care căutăm s-o minimizăm este deci $T{~m~}[i-1][S'] + T{~u~}[S'][S] + T{~c~}[S'][S]$. Calcularea directă a soluţiei pe baza recurenţelor de mai sus are complexitatea $O(M*N*2^N^ + M*2^N^*2^N^)$. Primul termen al complexităţii este dat de calcularea valorilor $T{~t~}$, iar al doilea de calcularea matricii $T{~m~}$.

Pentru valoarea rezultatului nu este important în ce ordine urcă şi coboară participanţii din plută, deci putem alege noi ordinea. Dacă aranjăm ordinea în doi paşi astfel încât în primul pas să urcăm participanţi, apoi în al doilea pas doar să coborâm participanţi, vom obţine o îmbunătăţire semnificativă a timpului de execuţie.

Pentru valoarea rezultatului nu este important în ce ordine urcă şi coboară participanţii din plută, deci putem alege noi ordinea. Dacă aranjăm ordinea în doi paşi astfel încât în primul pas să urcăm participanţi, apoi în al doilea pas doar să coborâm participanţi, vom obţine o îmbunătăţire semnificativă a timpului de execuţie. Se observă că dacă am efectua doar adăugări de elemente (daca în plută s-ar putea doar urca persoane, fără să poată coborî), atunci <tex> $S' \in S$ şi deci reprezentarea în cod binar a mulţimii $S'$ ar avea o valoare mai mică decât reprezentarea binară a mulţimii $S$. Dacă ar avea voie doar să coboare persoane, relaţia ar fi inversă. De aceea, vom ordona operaţiile de urcare şi coborâre astfel încât să aibă loc întâi toate urcările (astfel încât să putem parcurge crescător valorile binare ale mulţimilor) apoi toate coborârile (astfel încât să putem efectua a doua parcurgere, în ordine descrescătoare). Introducem două noi matrici auxiliare, $T{~ucm~}[i][S]$ şi $T{~um~}[i][S]$ care reprezintă timpul minim necesar la care se poate porni cu pluta de la punctul $i-1$ după ce au schimbat toţi locurile,