什么是动态规划？

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

img

  • 记忆化搜索 - 自顶向下的解决问题

  • 动态规划 - 自底向上的解决问题

0-1背包问题

F(n,C)考虑将 n 个物品放进容量为 c 的背包，使得价值最大。

状态转移方程如下：

F(i,c) = F(i-1,c)或 F(i,c) = v(i) + F(i-1, c-w(i))

即：

F(i,c) = max(F(i-1,c), v(i)+F(i-1,c-w(i)))

面试实战

  • Climbing Stairs(#70)

  • Integer Break(#343)

  • House Robber(#198)

  • Partition Equal Subset Sum(#416)

  • Longest Increasing Subsequence(#300)

  • dijkstra 单源最短路径算法也是动态规划

程序

具体实现：

见代码。