常见的 DP 优化：
优化状态：重新设计状态来减少时间/空间/代码复杂度，如状压 DP。
优化转移：用特定的方法来转移，使转移更快。
例题
力扣1871 跳跃游戏 (Gala Game)
设 \(dp[i]\) 为可否跳到 \(i\) 点。
转移：
\[dp[i]=\sum_{j=\max(0,i-maxJump)}^{\max(0,i-minJump)}dp[j]>0
\]
直接扫一遍的话，时间复杂度为 \(O(n^2)\)，会炸。
注意到没有修改，且求 \(dp[i]\) 所需要的 \(dp[j]\) 是连续的，那么不难想到前缀和。
时间复杂度降为 \(O(n)\) 可过。
这里就有了一个 DP 优化的流程：先打出暴力转移，然后看转移可以被什么方法优化。
一定要注意边界问题！搞清楚前缀和什么时候该 -1，什么时候直接取 0。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int dp[1000005],pre[1000005];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int L,R;string s;cin>>L>>R>>s;int n=s.size();dp[0]=1;for(int i=0;i<L;i++) pre[i]=1;for(int i=L;i<n;i++){int l=i-R,r=i-L;if(s[i]=='0') dp[i]=(pre[r]-(l<=0?0:pre[l-1])!=0);pre[i]=pre[i-1]+dp[i];}if(dp[n-1]) cout<<"Yes";else cout<<"No";return 0;
}
P2513 [HAOI2009] 逆序对数列
\(dp[i,j]\) 表示插入了前 \(i\) 个数，产生的逆序对为 \(j\) 的排列的方案数。
转移比较显然：
\[dp[i][j] = \sum_{k=0}^{\min(j, i-1)} dp[i-1][j-k]
\]
复杂度 \(O(n^2 k)\) 会炸。
发现这个转移式子就是上一行连续的一段，考虑前缀和优化。
定义前缀和数组：\(sum\)
\[sum[j] = \sum_{x=0}^{j} dp[i-1][x]
\]
转移变为：
\[dp[i][j] = sum[j] - sum[j-i]
\]
时间复杂度降为 \(O(nk)\) 可过。
还是那个思想：先写暴力转移，然后观察可以被什么方法优化。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[5005][5005];
int sum[5005];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n,k;cin>>n>>k;dp[1][0]=1;for(int i=2;i<=n;i++){sum[0]=dp[i-1][0];for(int j=1;j<=k;j++) sum[j]=(sum[j-1]+dp[i-1][j])%mod;for(int j=0;j<=k;j++){if(j<i) dp[i][j]=(sum[j]+mod)%mod;else dp[i][j]=(sum[j]-sum[j-i]+mod)%mod;}}cout<<dp[n][k];return 0;
}练习题：AT_dp_m Candies
P1107 [BJWC2008] 雷涛的小猫
牛客33634G 小人国的粉刷匠
ABC253E Distance Sequence
一定注意转移时的范围！极为容易因为小细节炸掉！