思考:背包问题对这道题目的启发(请大家来验证想法的正确性)
查看原帖
思考:背包问题对这道题目的启发(请大家来验证想法的正确性)
758581
name1ess_0123210楼主2024/11/11 10:14

关于背包问题的初始化:1.要求刚好装满背包,询问此条件下的最高价值,这样初始化(dp[0]=0,dp[1...V]=-INF)2.仅仅要求价值最大,这样初始化(dp[0...V]=0

类比到这道题,我们似乎可以把最终查询dp[r][c]的值看作恰好装满背包(而不是查询“不论最终到达何处,我只想拿最多的金币”(dp[0...r][0...c]=0)),这样就不需要考虑左下区域无法访问的情况了(也许这两种做法本质的逻辑是一样的?)

2024/11/11 10:14
加载中...