源码网站建设教程,马蜂窝是什么做的网站,局域网网站怎样做数据库,电子商务网站建设 下载拉勾教育版权所有#xff1a;https://kaiwu.lagou.com/course/courseInfo.htm?courseId3 动态规划思路
1.最优子结构 2.重复计算子机构 3.依靠递归#xff0c;层层向上传值#xff0c;所以编程时初始化子结构很重要
动态规划步骤
1.判断动态规划的类型 1.线性规划 https://kaiwu.lagou.com/course/courseInfo.htm?courseId3 动态规划思路
1.最优子结构 2.重复计算子机构 3.依靠递归层层向上传值所以编程时初始化子结构很重要
动态规划步骤
1.判断动态规划的类型 1.线性规划 一维数组 2.区间规划 二维数组 3.约束规划 对输出结果有限制并不是单纯的最优解 2.写出递归公式 3.编程实现 1.决定递推结果存储的数据结构一般为数组 2.初始化 3.实现递推逻辑 ##列子 1.线性规划 线性就是说各个子问题的规模以线性的方式分布并且子问题的最佳状态或结果可以存储在一维线性的数据结构里例如一维数组哈希表等。 解法中经常会用dp[i]去表示第i个位置的结果或者从0开始到第i个位置为止的最佳状态或结果。例如最长上升子序列。dp[i]表示从数组第0个元素开始到第i个元素为止的最长的上.
#####题目 LeetCode第198题给定一个数组不能选择相邻的数求如何选才能使总数最大。解法这道题需要运用经典的0-1思想简单说就是“选还是不选”。
2.区间规划 区间规划就是说各个子问题的规模由不同的区间来定义一般子问题的最佳状态或结果存储在二维数组里。一般用 dp[i][j] 代表从第 i 个位置到第 j 个位置之间的最佳状态或结果。
#####题目 举例LeetCode第516题在一个字符串S中求最长的回文子序列。例如给定字符串为dccac最长回文就是ccc。
对于回文来说必须保证两头的字符都相同。用dp[i][j]表示从字符串第i个字符到第j个字符之间的最长回文比较这段区间外的两个字符如果发现它们相等它们就肯定能构成新的最长回文。
当首尾的两个字符相等的时候 dp[0][n−1]dp[1][n−2] 2
否则dp[0][n−1]max(dp[1][n−1], dp[0][n−2])。
3.约束规划 与前面不通的它计算的不是最优子结构而是有条件的。 比如0-1背包它计算的不是背包最大的价值怎么装东西才能最大化而且还有一个重量的限定
