<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>

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'$, $T{~c~}[S'][S]$ este timpul necesar pentru coborârea participanţilor din plută, 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:

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:

<tex> $T_u[S_1][S_2] = \sum_{i \in S_2 - S_1}{s_i}$ </tex>
<tex> $T_c[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i}$ </tex>

<tex> $T_u[S_1][S_2] = \sum_{i \in S_2 - S_1}{s_i} = \sum_{i \in S_u}{s_i}$ </tex>
<tex> $T_c[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i} = \sum_{i \in S_c}{s_i}$ </tex>

<tex> $T_t[i][S] = \left\{
\begin{array}{l l}
  D_i & \quad \sum_{j \in S}{w_j} > c_i\\

Î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.
 
 
 

h2. Programare dinamica folosind vectori de numere intregi
h3(#problema-1). Problema 1: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)