动态规划

动态规划

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

主要思想

若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。

动态规划法仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量，

一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

动态规划模板步骤：

• 确定动态规划状态
• 写出状态转移方程（画出状态转移表）
• 考虑初始化条件
• 考虑输出状态
• 考虑对时间，空间复杂度的优化（Bonus）

算法应用

Leetcode 674.最长连续递增序列

思路

dp[i]：表示第i个元素，它的递增元素的个数。比如[1，3，5 ]元素3 从1递增到3 递增元素个数是2,dp[1]=2 初始化 dp=[1]*n 后比较

代码

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n=len(nums)
        if not nums or n<0:
            return 0
        dp=[1]*n
        for i in range(1,n):
            if nums[i]>nums[i-1]:
               dp[i]=dp[i-1]+1
        return max(dp)