Python|动态规划经典案例
动态规划原理
动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，最终获得原始问题的解，避免了对交叠子问题的重复求解。
动态规划要领
在动态规划算法中有三要素，即最优子结构、边界和状态转移函数。
最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到；
边界：问题最小子集的解；
状态转移函数：从一个阶段向另一个阶段过渡的具体模式，描述的是两个相邻子问题之间的关系。
最长上升子序列问题
给定一个无序的整数数组，找到其中最长上升子序列的长度。
1.示例
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
2.解题思路：
状态定义：
创建与输入列表nums相同长度的列表dp，dp[i]的值代表nums前i个数字的最长子序列长度。
3.最优子结构：
当计算dp[i]时，我们需要遍历[0,i)的列表区间做出判断（j∈[0,i））：
（1）当nums[i]>nums[j]时，此时为上升子序列，所以此时dp[i]=dp[j]+1
（2）当nums[i]>nums[j]时，此时不是上升子序列跳过
4.转移方程：dp[i]=max(dp[i],dp[j]+1)
5.初始状态：每个元素至少可以单独成为子序列，所有dp列表所有元素初始值为1
class Solution: def lengthOfLIS(self, nums) : len_nums=len(nums) dp=[1 for i in range(len_nums)] for i in range(1,len_nums): for j in range(i): if nums[i]>nums[j]: dp[i]=max(dp[i],dp[j]+1) return max(dp) |
|---|
总结
以上就是本篇文章全部内容，才开始学习动态规划的萌新没看懂不要着急，动态规划的代码是有迹可循的，需要大家多多练习类似的题目。对于大家来说这道题还有另外的解法，希望各位读者们多多交流，将你们的代码发表在留言区供大家参考。
END
主 编 | 王楠岚
责 编 | KeeCTh
能力越强，责任越大。实事求是，严谨细致。
——where2go 团队
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录