本文章可能不会继续更新，可以在单独的题解里面找找有没有有趣的DP题目。
这里不分类介绍具体的优化方法，而是收集一些比较有意思的题目，从题目出发讲优化。
一些优化手段：

• 单调队列原理及其应用 | KSkun’s Blog
• [HNOI2008]玩具装箱 题解 & DP斜率优化原理与实现 | KSkun’s Blog

[NOI2005]瑰丽华尔兹：从4次方到3次方

朴素的想法

这个题是一个DP问题，设计状态为dp[i, j, k]为在(i, j)处，k时间段末的滑行最长距离。考虑从上一时间段转移过来，如果不考虑障碍物，假设在第一坐标上移动，转移方程应该如下：
dp[i, j, k] = \max \{dp[i', j, k - 1] + i - i'\} \ (i - i' \leq t)
对于每一个时间段k，对于每一个点(i, j)进行时间段方向上的转移，单次转移遍历该方向的点，复杂度为1次。遍历地图的复杂度为2次，遍历时间段的复杂度为1次，总和即为4次。
对于200的数据，4次显然是不够的，考虑优化这一过程。

降低时间：单调队列

我们发现这个题可以维护区间上长度为t的一段 dp[i', j, k - 1] - i' 的最大值，这个过程可以用单调队列降掉1次。3次的复杂度是可以接受的。

降低空间：滚动数组

注意到转移只跟上一层即k-1有关系，这就可以对这一维进行滚动。空间减少1次。滚动数组对cache友好，还能优化下常数。

降低空间：降维

转移具有一定的方向性，如果按照一定顺序转移可以达到更新而不发生错误的效果。经过分析后，k这一维可以删去。

说了这么多，没代码说个**

那就给你们代码嘛。

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>

const int NINF = 0xc0c0c0c0;
const int fix[5][5] = {{0, -1, 1, 0, 0}, {0, 0, 0, -1, 1}};

int n, m, x, y, k, dp[205][205], si, ti, di, que[205], pos[205], l, r, v, now, ans = -1;
char mmp[205][205];

inline void workdp(int nx, int ny, int d, int t) {
    l = r = 1;
    now = 1;
    while(nx <= n && ny <= m && nx >= 1 && ny >= 1) {
        if(mmp[nx][ny] == 'x') {
            l = r = 1;
        }
        v = dp[nx][ny] - now;
        if(v >= NINF) {
            while(l < r && que[r - 1] <= v) r--;
            que[r] = v;
            pos[r] = now;
            r++;
        } 
        while(l < r && now - pos[l] > t) l++;
        if(l < r) {
            dp[nx][ny] = que[l] + now;
        } else {
            dp[nx][ny] = NINF;
        }
        ans = std::max(ans, dp[nx][ny]);
        nx += fix[0][d];
        ny += fix[1][d];
        now++;
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%s", mmp[i] + 1);
    }
    memset(dp, 0xc0, sizeof dp);
    dp[x][y] = 0;
    while(k--) {
        scanf("%d%d%d", &si, &ti, &di);
        if(di == 1) {
            for(int i = 1; i <= m; i++) workdp(n, i, di, ti - si + 1);
        }
        if(di == 2) {
            for(int i = 1; i <= m; i++) workdp(1, i, di, ti - si + 1);
        }
        if(di == 3) {
            for(int i = 1; i <= n; i++) workdp(i, m, di, ti - si + 1);
        }
        if(di == 4) {
            for(int i = 1; i <= n; i++) workdp(i, 1, di, ti - si + 1);
        }
    }
    printf("%d", ans);
    return 0;
}

宝物筛选_NOI导刊2010提高（02）：多重背包的二进制优化和单调队列优化

多重背包的二进制优化

说明

如果将一个数字拆成1, 2, 4, 8, \cdots , 2^n, n - 2^n这些数字，可以证明这些数字可以组合成1~n的任意一个数字，对每个物品的数量如此拆分，即可转换为01背包问题。这样的复杂度是O(V * \sum (\log n_i))的。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
} ip;

#define read ip.read

int n, w, val, wei, num, dp[40005], j;

int main() {
    n = read();
    w = read();
    for(int i = 1; i <= n; i++) {
        val = read();
        wei = read();
        num = read();
        for(j = 0; (1 << (j + 1)) - 1 <= num; j++) {
            for(int k = w; k >= wei * (1 << j); k--) {
                dp[k] = std::max(dp[k], dp[k - wei * (1 << j)] + val * (1 << j));
            }
        }
        if((1 << j) - 1 < num) {
            j = num - ((1 << j) - 1);
            for(int k = w; k >= wei * j; k--) {
                dp[k] = std::max(dp[k], dp[k - wei * j] + val * j);
            }
        }
    }
    printf("%d", dp[w]);
    return 0;
}

多重背包的单调队列优化

说明

回到最原始的转移方程：
dp[i][j] = \max \{dp[i - 1][j - k * c_i] + k * v_i\} \ (0 \leq k \leq \min (n_i, \lfloor \frac{j}{c_i} \rfloor))
这里的转移，一定是从比j小c_i整数倍的位置转移而来。我们可以讨论j模c_i的值，对一个剩余类内部进行单调队列的转移。从 (j \mod c_i) + k * c_i 这个状态往 (j \mod c_i) + k' * c_i \ (k' \geq k) 这个状态转移。这样做复杂度可以减为 O(V * N) 。
当然你还可以对i维度进行滚动数组优化空间。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
} ip;

#define read ip.read

inline int g(int i) {
    return i & 1;
} 

int n, w, val, wei, num, que[40005], pos[40005], l, r, dlt, v, dp[2][40005];

int main() {
    n = read();
    w = read();
    for(int i = 1; i <= n; i++) {
        val = read();
        wei = read();
        num = read();
        for(int j = 0; j < wei; j++) {
            l = r = 1;
            dlt = 0;
            for(int k = 0; j + k * wei <= w; k++) {
                v = dp[g(i - 1)][j + k * wei] - dlt;
                while(l < r && que[r - 1] <= v) r--;
                que[r] = v;
                pos[r] = k;
                r++;
                while(l < r && k - pos[l] > num) l++;
                dp[g(i)][j + k * wei] = std::max(dp[g(i)][j + k * wei], que[l] + dlt);
                dlt += val;
            }
        }
    }
    printf("%d", dp[g(n)][w]);
    return 0;
}

[NOIP2009普及]道路游戏：转化单调队列

详细分析见[NOIP2009普及]道路游戏 题解 | KSkun’s Blog。