一、定义
动态规划（dynamic programming)简称DP，用于解决重叠子问题。
二、解题步骤
1、确定dp数组以及下标含义
2、确定状态转移方程
3、dp数组的初始化
题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。
- 恰好装满。只需要初始化dp[0] 为 0， 其他初始化为负数即可。
- 可以不装满。 只需要全部初始化为 0，即可。
4、确定遍历的顺序
外层遍历物品，还是外层遍历容量；
以及容量从大到小遍历，还是从小到大遍历。
5、举例检验
三、总结
递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
动态规划内容很多，将从以下方面进行学习：
斐波拉契数列
背包（0-1背包，完全背包）。。。。。
参考资料：github分类详解
一、定义 动态规划（dynamic programming)简称DP，用于解决重叠子问题。 二、解题步骤 1、确定...
解题思路： 用动态规划得到dp[i] represents the largest divisible subse...
题意 样例 注意事项 1.解题思路 这道题肯定使用动态规划来解决，解决动态规划的问题通常来说，难点在于动态规划...
题目描述 考点 动态规划 广度优先搜索 解题思路一：动态规划 状态定义：dp[i]表示数字i最少可以由几个完全平方...
动态规划 通过子问题递推求解最优的方法， 动态规划常常适用于有重叠子问题和最优子结构性质的问题 。 解题思路 动态...
题目描述 考点 动态规划 解题思路 使用动态规划：我们从左上角到右下角进行一次动态搜索，再从右下到左上进行一次动态...
题目描述 一、CPP 1. 动态规划法： 解题思路:详解异步动态规划笔记——类型二：计数型。 时间复杂度:O(n2...
解题思路 基本思路是动态规划dp数组来记录爬i+1阶楼梯所需要的方法，dp数组在动态规划时，往往记录结果重点是确定...
53.最大子数组和[https://leetcode.cn/problems/maximum-subarray/]...
leetcode 53题 解题思路：动态规划问题。给出数组array[ ]，假定 f(i)代表array数组中以a...
本文标题：动态规划之解题思路
本文链接：https://www.haomeiwen.com/subject/celblltx.html
网友评论