分享一个简单线性dp

我们可以o(n^2)，枚举每一个布告，然后从后往前枚举i前面的位置，然后状态转移

void solve() {int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];vector<int> f(n + 1, 0x3f3f3f3f);f[0] = 0;for (int i = 1; i <= n; i++) {for (int j = i - 1; j >= 0; j--) {if (j + a[i] >= i) {if (j + a[i] <= n) f[j + a[i]] = min(f[j + a[i]], f[j] + 1);}}}if (f[n] >= 0x3f3f3f3f) f[n] = -1;cout << f[n] << endl;
}