dp.tex

\section{Dynamic Programming}

\subsection{LCS (Longest Common Subsequence)}

\begin{verbatim}
int L[MAX][MAX] = {{0}};
int LCS(char A[], char B[]) {
   for (int i = m;i >= 0; i--) {     /* m = strlen(A) */
      for (int j = n;j >= 0; j--) {  /* n = strlen(B) */
         if (!A[i] || !B[j])
            L[i][j] = 0;
         else if (A[i] == B[j])
            L[i][j] = 1 + L[i+1][j+1];
         else L[i][j] = max(L[i+1][j], L[i][j+1]);
      }
   }
   return L[0][0];
}

int LCSString(int L[MAX][MAX]) {
   int i, j;
   i = j = 0;
   while (i < m && j < n) {
      if (A[i] == B[j]) {
         poe A[i] no fim da str-solucao
         i++; j++;
      }      
      if (L[i+1][j] >= L[i][j+1]) i++;
      else j++;
   }
}

\end{verbatim}

\subsection{LIS (Longest Increasing Subsequence)}

\begin{verbatim}
int pred[MAX_SIZE],lasti;
int LIS(int C[], int n) {
   int s[MAX_SIZE], max=INT_MIN;
   for (int i = 1; i < n; i++) {
       for (int j = 0; j < i; i++) {
           if (C[i] > C[j] && s[i] <= s[j]) {
              pred[i] = j;
              if ((s[i] = s[j] + 1) > max)
                 lasti = i;
                 max = s[i];
           }
       }
   }
   return max;
}

void PrintLIS() {
   int i, j, aux[MAX_SIZE];
   for (j = max-1, i = lasti; j >= 0; j--) {
      aux[j] = C[i];
      i = pred[i];
   }
   
   for (j = 0;j < max; j++)
      printf(``%d\n'', aux[j]);
}
\end{verbatim}

\subsection{MCM (Matrix Chain Multiplication)}
\begin{verbatim}
int Calc(int i, int j) {
    int res = INT_MAX;
    for (k = i;k < j; k++) {
        tmp = m[i][k] + m[k+1][j]+
            Line[i] * Col[k] * Col[j];
        if (tmp < res) {
           res = tmp;
           s[i][j] = k;
        }
    }
    return res;
}

void MCM() {
    int i, j, n = 3;
    for (i = 0;i < n; i++)
        m[i][i] = 0;

    for (i = n-1; i >= 0; i--)
        for (j = i + 1; j <= n; j++)
            m[i][j] = Calc(i, j);
}

//PrintMCM(0,N-1);
void PrintMCM(int i, int j) {
    if (i == j) printf("A%d",i);
    else {
        putchar('(');
        PrintMCM(i, s[i][j]);
        putchar('*');
        PrintMCM(s[i][j] + 1, j);
        putchar(')');
    }
}
\end{verbatim}

\subsection{Knapsack}

\begin{verbatim}
int n[WSIZE][ISIZE] = {{0}}
/*
 * put one zero in weight and value;
 * ex: weight={>0<,3,4,5} & value={>0<,3,4,5,6};
 */
int knapsack(int items, int W,
             int value[], int weight[]){
   for (int i = 1;i <= items; i++) {
      for (int j = 0; j <= W; j++) {
         if (weight[i] <= j) {
            if (value[i] + n[i-1][j-weight[i]]
               > n[i-1][j])
               n[i][j] = value[i] +
                         n[i-1][j-weight[i]];
            else n[i][j]=n[i-1][j];
         } else n[i][j]=n[i-1][j];
      }
   }
   return n[items][W];
}

void print_sequence(int items, int W, int weight[]) {
   int i = items, k = W;
   while (i > 0 && k > 0) {
      if (n[i][k] != n[i-1][k]) {
         printf("item %d is in\n", i);
         k = k-weight[i-1];
      }
      i--;
   }
}
\end{verbatim}

\subsection{Counting Change}
De quantas maneiras podemos obter um dado valor $N$, usando somente moedas com determinados valores.
\begin{verbatim}
int coins[] = {50,25,10,5,1};
int CoinChange(int n) {
  table[0] = 1;
  for (i = 0; i < 5; i++) {
    c = coins[i];
    for (j = c; j <= n; j++)
      table[j] += table[j - c];
  }
  return table[n];
}
\end{verbatim}

\subsection{Coin Changing}

Dada uma lista de $N$ moedas e seus valores $(V_1,V_2,\ldots, V_n)$ e uma soma total $S$, determine o menor número de moedas da lista cuja soma seja $S$.
\begin{verbatim}
int n[10000],i,N, coins[]={50,25,10,5,1},k;
int main() {
    scanf("%d", &N);
    for (int i = 0; i <= N; i++) n[i] = INT_MAX;
    n[0] = 0;
    for (int i = 0; i < 5; i++)
        for (k = 0;k <= N - coins[i]; k++)
            n[k + coins[i]] =
               min(n[k] + 1, n[k + coins[i]]);
    printf("%d\n", n[N]);
    return 0;
}
\end{verbatim}

\subsection{Biggest Sum}

\begin{verbatim}
#define SIZE 20000
int n[SIZE];

int main() {
   int k, s, b;
   int xl, xr, best, prevx;
   
   cin>>k;
   for (int i = 1; i <= k; i++) {
      xr = xl = 0;
      
      cin >> s;
      for (int j = 0; j < s - 1; j++)
         cin >> n[j];
         
      prevx = xl = xr = 0;
      best = b = n[0];
      for (int j = 1; j < s - 1; j++) {
         if (b < 0)
            prevx = j;
         b = n[j] + max(0, b);
         if (b > best || 
             (b == best && j - prevx > xr - xl)) {
            xl = prevx;
            xr = j;
            best = b;
         }
      }
      if (best > 0)
         cout<<"The nicest part of route "<<i<<" 
               is between stops "<<xl+1<<" 
               and "<<xr+2<<endl;
   }
   return 0;
}
\end{verbatim}

\subsection{Edit Distance}
\begin{enumerate}
\item Delete a character
\item Insert a new character
\item Replace a letter
\end{enumerate}

\begin{verbatim}
int DE(char *str1, char *str2) {
    int n[SIZE][SIZE];
    int i, j, value;

    for (i = 0; i <= str1_len; i++) n[i][0] = i;
    for (j = 0; j <= str2_len; j++) n[0][j] = j;

    for (i = 1; i <= str1_len; i++) {
        for (j = 1;j <= str2_len; j++) {
            value = (str1[i - 1] != str2[j - 1]);

            n[i][j] = min(n[i - 1][j - 1] + value,
                    n[i - 1][j] + 1,
                    n[i][j - 1] + 1);
        }
    }
    return n[str1_len][str2_len];
}
\end{verbatim}
\begin{verbatim}
T(i,j) = \min(C_d + T(i-1,j),
             T(i, j-1) + C_i,
             T(i-1, j-1) + (A[i]==B[j] ? 0 : C_r))
\end{verbatim}

\subsection{Integer Partitions}
$P(n)$ represents the number of possible partitions of a natural number $n$.
$P(4)=5,{{4},{3+1},{2+2},{2+1+1},{1+1+1+1}}$\\
$P(0)=1$\\
$P(n)=0, n<0$\\
$P(n)=p(1,n)$\\
$p(k,n)=p(k+1,n)+p(k,n-k)$\\
$p(k,n)=0$ if $k>n$\\
$p(k,n)=1$ if $k=n$

\subsection{Box Stacking}
A set of boxes is given. $Box_i={h_i, w_i, d_i}$.\\
We can only stack box $i$ on box $j$ if $w_i<w_j$ and $d_i<d_j$.\\
To consider all the orientations of the boxes, replace each box with $3$ boxes such that $w_i\le d_i$ and $box_1[0]=h_i,box_2[0]=w_i,box_3[0]=d_i$.\\
Then, sort the boxes by decreasing area($w_i*d_i)$.\\
$H(j)=$tallest stack of boxes with box $j$ on top.\\
$H(j)=\max_{i<j \& w_i>w_j \& d_i>dj}(H(i))+h_j$\\
Check $H(j)$ for all values of $j$.\\

\subsection{Building Bridges}
Maximize number of non-crossing bridges.
Ex:\\
bridge1:$2,5,1,n,\cdots,4,3$\\
bridge2:$1,2,3,4,\cdots,n$\\
Let $X(i)$ be the index of the corresponding city on northern bank. $X(1) =3, X(2)=1,\ldots$.\\
Find longest increasing subsequence of $X(1),\cdots ,X(n)$.

\subsection{Partition Problem}
\textbf{Input:} A given arrangement $S$ of non-negative numbers ${s_1,\ldots,s_n}$ and an integer $k$.\\
\textbf{Output:} Partition $S$ into $k$ ranges, so as to minimize the maximum sum over all the ranges.\\

\begin{verbatim}
int M[1000][100], D[1000][100];
void partition_i(vector<int> &v, int k) {
   int p[1000], i, n = v.size();
   v.insert(v.begin(),0);
   p[0] = 0;
   for(i = 1;i < v.size(); i++)
      p[i] = p[i - 1] + v[i];
      
   for (i = 1; i <= n; i++)
      M[i][1]=p[i];
   for (i = 1; i <= k; i++)
      M[1][i] = v[1];
   for (i = 2; i <= n; i++) {
      for (int j = 2; j<=k; j++) {
         M[i][j] = INT_MAX<<1 - 1;
	       int s = 0;
	       for (int x = 1; x <= i - 1; x++) {
		        s = max(M[x][j-1], p[i] - p[x]);
		        if (M[i][j] > s) {
		           M[i][j] = s;
		           D[i][j] = x;
		        }
	       }
	    }
   }
   printf("%d\n", M[n][k]);
}
//n = number of elements of the initial set
void reconstruct_partition(
     const vector<int> &S, int n, int k) {
   if (k == 1) {
	    for (int i = 1; i <= n; i++)
	       printf("%d ", S[i]);
	    putchar('\n');
   } else {
	    reconstruct_partition(S, D[n][k], k - 1);
	    for (int i = D[n][k] + 1; i<= n; i++)
	       printf("%d ", S[i]);
	    putchar('\n');
   }
}
\end{verbatim}

\subsection{Balanced Partition}
\begin{verbatim}

enum {DONT_GET, GET};
char **sol, **P;

// return 1 if there is a subset of v0...vi with sum j
// 0 otherwise
int calcP(int i, int j, const vi &v) {
   if (i < 0 || j < 0) return 0;
   if (P[i][j] != -1) return P[i][j];

   if (j == 0) { // trivial case
       sol[i][j] = DONT_GET;
       return P[i][j] = 1; 
   }  
   if (v[i] == j) {
      sol[i][j] = GET;
      return P[i][j] = 1;
   }

   int res1 = calcP(i - 1, j, v);
   int res2 = calcP(i - 1, j - v[i], v);
   if (res1 >= res2)
      P[i][j] = res1, sol[i][j] = DONT_GET;
   else P[i][j] = res2, sol[i][j] = GET;
   return P[i][j];
}


// v is the vector of values
// k is the maximum value in v
// sum is the sum of all elements in v
void balanced_partition(vi &v, int k, int sum) {
   P = new char*[v.size()];
   sol = new char*[v.size()];
   for (int i = 0; i < v.size(); i++) {
      P[i] = new char[k * v.size() + 1];
      sol[i] = new char[k * v.size() + 1];
      for (int j = 0; j < k * v.size() + 1; j++)
         P[i][j] = -1, sol[i][j] = DONT_GET;
   }
   for (int i = 0; i < v.size(); i++)
      for (int j = 0; j < v.size() * k + 1; j++)
         calcP(i, j, v);
   //calcP(v.size() - 1, sum/2, v);

   int S = sum / 2;
   if (sum & 1 || !P[v.size() - 1][S])
       cout << "ERROR" <<endl;
   else cout << "SUCCESS" << endl;
}

void free_mem(vi& v) {
    for (int i = 0; i < v.size(); i++) {
        delete P[i]; delete sol[i];
    }
    delete[] P;
    delete[] sol;
}

// get_solution(v.size() - 1, accumulate(v.begin(), v.end(), 0) / 2,
// v1, v2, v);
void get_solution(int i, int j,
                  vi &S1, vi &S2, vi &v) {
   if (j < 0 || i < 0) return;
   if (sol[i][j] == GET) {
      S1.push_back(v[i]);
      return get_solution(i - 1, j - v[i], S1 ,S2, v);
   } else {
      S2.push_back(v[i]);
      return get_solution(i - 1, j, S1, S2, v);
   }
}
\end{verbatim}