Рюкзак
------------------------
dp[i][w], i - индекс объекта, w - набранный вес
dp[0][w]=0

dp[i][w] = max(dp[i-1][w],dp[i-1][w-w_i]+c+1)
                     ^        ^
              не взяли        i-й взяли

====================================

vector <int> w,c;
int W, n;
vector<int> prev(w+1);
vector<int> cur(w+1);
vector <vector <int>> dp(n+1, vector<int> (w+1));
for(int i=1; i<=n; ++i) {
  for(int j=w[i-1]; j<=w; ++j) cur[j] = max(prev[j], prev[j-w[i-1]+c[i-1]);
  for(int j=0; j<w[i-1];++j) cur[j]=prev[j];
  prev.swap(cur);
}

|||||||||||
LCS
-------------
A[1..n]
B[1..m]
LCS(An,Bm)=max(if A[n]=B[m] LCS(An-1,Bm-1)+1; else ? LCS(A_n, B_m-1) : LCS(A_n-1, B_m))
==============================
string a,b;
int n,m;
vector<vector <int>> dp(n+1, vector<int>(m+1));
for(int i=1;i<=n;++i) {
  for(int j=1;j!=m;++j) {
    if(a[i-1]==b[j-1]) {
      dp[i][j]=dp[i-1][j-1]+1;
    }
    dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
  }
}

|||||||||||||||||
MultiMatrix
----------------------
n - количество матриц
row-строки; с-столбцы
dp[l][r]=min(dp[l][k]+dp[k+1][r]+row[l]*c[l]*c[k]);
          ^
         l<=k<r
dp[1][1]=0;
==========================
int dp(int l, int r, vector<vector <int>>& memo) {
  if(l==r) return 0;
  int result=dp(l, l, memo)+dp(l+1, r, memo)+rows[l]*cols[r]*cols[l];
  for(int k=l+1;k<r;++i) {
    result =min(result, dp(l,k,memo)+dp(k+1,r,memo)+rows[l]*cols[r]*cols[k]);
  }
  memo[l][r]=result;
  return result;
}