Question

动态规划之解题思路

Answer 1

一、定义

动态规划（dynamic programming)简称DP，用于解决重叠子问题。

二、解题步骤

1、确定dp数组以及下标含义

2、确定状态转移方程

3、dp数组的初始化

题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。

- 恰好装满。只需要初始化dp[0] 为 0， 其他初始化为负数即可。

- 可以不装满。 只需要全部初始化为 0，即可。

4、确定遍历的顺序

外层遍历物品，还是外层遍历容量；

以及容量从大到小遍历，还是从小到大遍历。

5、举例检验

三、总结

递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。

动态规划内容很多，将从以下方面进行学习：

斐波拉契数列

背包（0-1背包，完全背包）。。。。。

参考资料： github分类详解