本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理
以下文章来源于腾讯云 作者：算法与编程之美
( 想要学习Python？Python学习交流群：1039649593，满足你的需求，资料都已经上传群文件流，可以自行下载！还有海量最新2020python学习资料。 )
动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，最终获得原始问题的解，避免了对交叠子问题的重复求解。
在动态规划算法中有三要素，即最优子结构、边界和状态转移函数。
最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到；
边界：问题最小子集的解；
状态转移函数：从一个阶段向另一个阶段过渡的具体模式，描述的是两个相邻子问题之间的关系。
给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
状态定义：
创建与输入列表nums相同长度的列表dp，dp[i]的值代表nums前i个数字的最长子序列长度。
当计算dp[i]时，我们需要遍历[0,i)的列表区间做出判断（j∈[0,i））：
（1）当nums[i]>nums[j]时，此时为上升子序列，所以此时dp[i]=dp[j]+1
（2）当nums[i]>nums[j]时，此时不是上升子序列跳过
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)
以上就是本篇文章全部内容，才开始学习动态规划的萌新没看懂不要着急，动态规划的代码是有迹可循的，需要大家多多练习类似的题目。对于大家来说这道题还有另外的解法，希望各位读者们多多交流，将你们的代码发表在留言区供大家参考。
原文：https://www.cnblogs.com/aa1273935919/p/13993894.html