P1282多米诺骨牌
容易发现一个性质：对于前\(i\)个牌子，它们的点数总和加起来是一个定值。所以，设\(f[i][j]\)表示前\(i\)个多米诺骨牌的第一行的和为j时的最小旋转次数。
状态转移方程：
初始化：
\(f[1][a[1]]=0;f[1][b[1]]=1;\)其余全部是正无穷
P4138挂饰
设\(f[i][j]\)表示前\(i\)个物品，剩余
至少\(j\)个空挂钩时的最大喜悦值。
状态转移方程：
初始化：\(f[0][1]=0\)，其余全部是负无穷
需要注意的是，在\(DP\)前要按照挂钩的数量从大到小排序，因为排序之后才能使挂钩数量尽可能多，越有可能使得结果更优。如果不排序，可能很快就没有了挂钩，错过了后面权值特别大的点。
P2679子串
设\(f[i][j][k]\)表示从A串的前i个字符中取k个不重复子串，拼接起来后与B的前j个子串相等的方案数量。
状态转移方程：
\(f[i][j][k]=\)
\(f[i-1][j][k],if(a[i]!=b[j])\)
\(f[i-1][j][k]+f[i-1][j-1][k-1],if(a[i]==b[j],a[i-1]!=b[j-1])\)
\(f[i-1][j][k]+f[i-1][j-1][k-1]+f[i-1][j-2][k-1],if(a[i]==b[j],a[i-1]==b[j-1],a[i-2]!=b[j-2])\)
......
如果直接算，时间复杂度是\(O(nm^2k)\)，明显超时。这时我们可以用前缀和来优化\(DP\)，时间复杂度会降至\(O(nmk)\)。
另外，此时的空间复杂度为\(1000\times200\times 200\times2\)（开\(long\) \(long\)），也就是8e7，也会爆炸。观察式子，我们可以发现每一次转移都是\(f[i-1][...]\)转移到\(f[i][...]\)，所以我们可以直接滚掉第一维，将空间复杂度优化到\(200*200*2\)。
P5662 [CSP-J2019] 纪念品
题目中有一句关键的话“每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。”我们可以根据这句话简化问题：把第\(i\)天买入，第\(j\)天卖出看作：第\(i\)天买入，第\(i+1\)天卖出，第\(i+1\)天买入，第\(i+2\)天卖出......第\(j-1\)天买入，第\(j\)天卖出。这时就可以将当天的价格看作体积，将当天与后一天的价格差当做价值，进行完全背包。
设f[i][j][k]表示第i天，前j个物品，手中的钱数为k时候的最大收益。状态转移方程：
考虑滚动数组，我们发现只需要保留\(k\)这一维即可。
P4059找爸爸
首先要知道，两个序列的某一个位置都是空格的情况肯定不是最优解。因为题目中k的系数是负数，k增加会令答案更劣。所以对于一个位置只考虑三种情况：
1：\(A\)和\(B\)都不是空格
2：\(A\)是空格，\(B\)不是
3：\(A\)不是空格，\(B\)是
设\(dp[i][j][0/1/2]\)表示\(A\)的\(0\)$i-1$和$B$的$0$\(j-1\)匹配，且最后一位分别是情况\(1,2,3\)时的最优解。
初始化：\(dp[0][i][1]=-a-b*(i-1),dp[0][i][0]=dp[0][i][2]=-1e9\)
\(dp[i][0][2]=-a-b*(i-1),dp[i][0][0]=dp[i][0][1]=-1e9\)
\(dp[0][0][1]=dp[0][0][2]=-1e9\)
状态转移方程：
\(f[i][j][0]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]))+d[x[i-1]][y[j-1]];\)
\(f[i][j][1]=max(f[i][j-1][0]-a,max(f[i][j-1][1]-b,f[i][j-1][2]-a));\)
\(f[i][j][2]=max(f[i-1][j][0]-a,max(f[i-1][j][1]-a,f[i-1][j][2]-b));\)
P7961 [NOIP2021]数列
考虑按照 \(S\) 的二进制位数进行 \(DP\)
设 \(f[i][j][k][l]\) 表示当前是 \(S\) 从低到高的第 \(i\) 位，已经确定了 \(j\) 个序列 \(a\) 中的元素， \(S\) 从低到高前 \(i\) 位中有 \(k\) 个 \(1\) ，向第 \(i\) 位的下一位进位 \(l\) 。
如果从前面转移到 \(f[i][j][k][l]\) ，细节太多，不好写。所以考虑从 \(f[i][j][k][l]\) 往后转移。
假设当前序列 \(a\) 中分配了 \(t\) 个元素的值为 \(i\) ，加上上一位进过来的 \(l\) 个 \(1\) ，总共要向下一位进位\(t+l\)，下一位进位的时候要进位 \((t+l)/2\) .
\(f[i][j][k][l]\) 往后要转移的状态是： \(f[i+1][j+t][k+(t+l)\) \(mod\) \(2][(l+p)/2]\)
状态转移方程：
\(f[i+1][j+t][k+(t+l)\) \(mod\) \(2][(l+p)/2]\)
\(=f[i][j][k][l]\times v^t_i\times C(n-j,t)\)