Name		Name	Last commit message	Last commit date
parent directory ..
121-best-time-to-buy-and-sell-stock.md		121-best-time-to-buy-and-sell-stock.md
122-best-time-to-buy-and-sell-stock-ii.md		122-best-time-to-buy-and-sell-stock-ii.md
139-word-break.md		139-word-break.md
221-maximal-square.md		221-maximal-square.md
300-longest-increasing-subsequence.md		300-longest-increasing-subsequence.md
53-maximum-subarray.md		53-maximum-subarray.md
lint109-triangle.md		lint109-triangle.md
lint110-minimum-path-sum.md		lint110-minimum-path-sum.md
lint111-climbing-stairs.md		lint111-climbing-stairs.md
lint114-unique-paths.md		lint114-unique-paths.md
lint115-unique-paths-ii.md		lint115-unique-paths-ii.md
lint116-jump-game.md		lint116-jump-game.md
lint117-jump-game-ii.md		lint117-jump-game-ii.md
lint125-backpack-ii.md		lint125-backpack-ii.md
lint397-longest-increasing-continuous-subsequence.md		lint397-longest-increasing-continuous-subsequence.md
lint42-maximum-subarray-ii.md		lint42-maximum-subarray-ii.md
lint77-longest-common-subsequence.md		lint77-longest-common-subsequence.md
lint92-backpack.md		lint92-backpack.md
readme.md		readme.md

readme.md

这些是动态规划的题目

背包问题

背包九讲

0-1背包初始化

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它F[1..V ] 均设为 −∞，这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F[0..V ]全部设为 0。

完全背包问题

F[0..V ] ←0
for i ← 1 to N
	for v ← Ci to V
		F[v] ← max(F[v], F[v − Ci] + Wi)

code_interview/DynamicProgram at master · DragonFive/code_interview · GitHub

Expand file tree

Breadcrumbs

DynamicProgram

Directory actions

More options

Directory actions

More options

Latest commit

History