动态规划之解题思路
发布网友
发布时间：2022-12-03 21:11
共1个回答
热心网友
时间：2023-11-19 02:44
动态规划（dynamic programming)简称DP，用于解决重叠子问题。
二、解题步骤
1、确定dp数组以及下标含义
2、确定状态转移方程
3、dp数组的初始化
题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。
- 恰好装满。只需要初始化dp[0] 为 0， 其他初始化为负数即可。
- 可以不装满。 只需要全部初始化为 0，即可。
4、确定遍历的顺序
外层遍历物品，还是外层遍历容量；
以及容量从大到小遍历，还是从小到大遍历。
5、举例检验
三、总结
递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
动态规划内容很多，将从以下方面进行学习：
斐波拉契数列
背包（0-1背包，完全背包）。。。。。
参考资料： github分类详解
