边界dp注意重叠边界
前言：这个题目感觉不是简单的背包问题，因为我们这个是有限制的
想到了之前写的边界的dp，本来想定义二维dp，发现没必要二维dp，一维dp就够了，dp[i] 表示填充 1 - i 需要的最少的数量，符合子问题的定义，但是我们需要处理好边界问题，不能有重复
题目地址
#include<bits/stdc++.h>
using namespace std;#define int long long
int t;
int n;
const int N = (int)5e3+10;
int a[N];
// dp[ i ][ r ][ 0 / 1 ]
int dp[N];signed main(){cin >> t;while(t--){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];//memset(dp,0x3fffffff,sizeof dp);for(int i=0;i<=n;i++){dp[i] = 0x3fffffff;}dp[0] = 0; // 处理好重叠的问题 for(int i=1;i<=n;i++){int u = a[i];for(int j=max(0ll,i-u);j<i;j++){if(dp[j]+1<dp[j+u]){dp[j+u] = dp[j]+1;}}} if(dp[n]!=0x3fffffff)cout << dp[n] << endl;else cout << -1 << endl;}return 0;
}
按照题解，这个确实是可以弄成一个背包问题
t = int(input())from math import inf
def solve():n = int(input())arr = list(map(int, input().split()))dp = [inf] * (n + 1)dp[0] = 0for (i, v) in enumerate(arr):for j in range(n - v, -1, -1):if j <= i and j + v > i:dp[j + v] = min(dp[j + v], dp[j] + 1)if dp[-1] == inf:print (-1)else:print (dp[-1])for _ in range(t):solve()