可以啊,为啥不行
by Zi_Gao @ 2023-11-18 21:55:32
@[Zi_Gao](/user/554698)
dp[i-k][k]和dp[i-1][k-1]这起码需要用两行列表储存吧?而且不一样的i和k需要的指定行也不一样。
by Operation0701 @ 2023-11-18 22:07:12
@[Operation0701](/user/1170071) 额,那这和背包那里像了。
学而不思则罔,思而不学则殆。
by Zi_Gao @ 2023-11-18 22:50:21
```python
T,M = map(int,input().split())
#dp = [[0]*T for _ in range(M)]
#d = {}
#for i in range(M):
# d[i] = tuple(map(int,input().split()))
#maxvalue = 0
for i in range(M):
for j in range(T):
if d[i][0]-1 > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-d[i][0]+1]+d[i][1])
#if dp[i][j] > maxvalue:
#maxvalue = dp[i][j]
print(maxvalue)
```
大佬你看背包的核心部分,动态转移方程那里,结构和这题的动态转移方程是一样的。
by Operation0701 @ 2023-11-18 23:14:22
@[Operation0701](/user/1170071) 都是记忆化搜索罢了吧
by xuyao35 @ 2024-04-29 12:27:42