请问01背包问题的dp数组一定要dp[0][j]的初始化吗？
来源：9-5 0-1背包问题
夜的钢琴曲5
2020-03-15
波波老师好，我今天字节笔试第二题01背包变种因为太久没做过，只AC了20%，悔不当初，看了下很多博客和老师的视频，发现有点出入，就是dp【0】【j】的初始化很多博客的方法里没写这一步，就是用j和W【0】比较来初始化这一部分，请问这部分是必要的吗？
写回答
1回答
-
对的，01 背包的 dp 初始化可以靠你说的方式“省略”。但是状态稍微有些不同。如果你仔细研究代码，就会发现，在这种情况下，dp 需要的大小是 dp[n + 1][W]，而不是课程中介绍的 dp[n][W]。
在这个课程中，我认为这种省略的方式虽然代码更简洁，但是思维跨度上要高一些，所以选择了我认为最直观理解的方式讲解。虽然多了一步显式的初始化。
当然，我说“思维跨度上要高一些”，也没有那么高。如果理解了我讲的方式，理解这个更简洁的代码，我相信是不难的。
加油！：）
012020-03-16
相似问题