算法合集

一、動态規劃 

1、最長回文字元串 Longest Symmetric String

int len = s.length(), ans = 1;
for(int i = 0; i < len; i++) {
    dp[i][i] = 1;
    if(i < len - 1 && s[i] == s[i+1]) {
        dp[i][i+1] = 1;
        ans = 2;
    }
}
for(int L = 3; L <= len; L++) {
    for(int i = 0; i + L - 1 < len; i++) {
        int j = i + L -1;
        if(s[i] == s[j] && dp[i+1][j-1] == 1) {
            dp[i][j] = 1;
            ans = L;
        }
    }
}
           

2、最⼤連續⼦序列和

dp[0] = a[0];
for(int i = 1; i < n; i++)
  dp[i] = max(a[i], dp[i-1]+a[i]);

int maxn = dp[0];
for(int i = 1; i < n; i++)
  maxn = max(dp[i], maxn);
           

3、最長不下降子序列 LIS

int ans = 0;
for(int i = 0; i < n; i++) {
    for(int j = 1; j < i; j++) {
      if(a[i] >= a[j])  dp[i] = max(1, dp[j] + 1);
    }
    ans = max(dp[i], ans);
}
//dp[i]表示必須以a[i]結尾的最長不下降子序列的長度
//dp[i] = max{1, dp[j] + 1}; // j從1 ~ i-1 且必須滿足a[j] <= a[i]
           

4、最長公共子序列 LCS

for(int i = 0; i <= lena; i++) dp[i][0] = 0;
for(int j = 0; j <= lenb; j++) dp[0][j] = 0;

for(int i =1; i <= lena; i++) {
    for(int j - 1; j <= lenb; j++) {
      if(a[i] == b[j])
            dp[i][j] = dp[i-1][j-1] + 1;
      else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
}
//dp[i][j]表示A的第i位之前和B的第i位之前的這兩個序列的LCS最長公共子序列的長度（下标從1開始）
//那麼dp[lena][lenb]即為所求
//遞推方程：
//當a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
//當a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
//邊界：dp[i][0] = dp[0][j] = 0(0 <= i <= n, 1 <= j <= m)
           

5、01背包

for(int i = 1; i <= n; i++) {
for(int j = 1, j <= v; j++)
  if(j < w[i]) 
    dp[i][j] = dp[i-1][j];
    else 
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
}
//dp[i][j]表示前i件物品恰好裝入容量為j的背包所能獲得的最大價值不放第i件物品，則dp[i][j] = dp[i-1][j]
//放第i件物品，那麼問題轉化為前i - 1件物品恰好裝入容量j - w[i]的背包中所能獲得的最大價值dp[i-1][j-w[i]] + c[i]
//遞推方程 dp[i][j] = max{ dp[i-1][j], dp[i-1][j-w[i]]+c[i] }
           

一維：

for(int i = 1; i <= n; i++) {
for(int j = v; j >= w[i]; j--)
  dp[v] = max(dp[v], dp[v[w[i]]] + c[i]);
}
           

6、完全背包

for(int i =1; i <= n; i++) {
    for(int j = w[i]; j <= v; j++)
    dp[j] = max(dp[i], dp[j-w[j]]+ c[i]);
}

//遞推方程：dp[i][j] = max(dp[i-1][v], dp[i][j-w[i]] + c[i])

//和01背包不同，這裡的j的枚舉順序為正向枚舉,而且是dp[i][j-w[i]]