Skip to content

DynamicProgram

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

DynamicProgram

Folders and files

NameName
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)