leetcode中的练习题----------动态规划

客官°小女子只卖身不卖艺 2022-04-24 10:54 146阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

解决方法：

动态规划三要素：最优子结构，边界，状态转移函数。  
最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或者某些状态直接得到，子问题的最优解能够决定这个问题的最优解。  
边界：问题最小子集的解。  
状态转移函数：一个阶段向另一个阶段过度的具体形式，两个相邻子问题之间的关系。  
重叠子问题：对于每个子问题的结果只计算一次，将结果保存，下一次需要上一个子问题的结果时只需要调用。就是利用空间换时间。  
对于这个题：  
第一个最优是-2，  
第二个最优是1+ -2=-1没有1大，所以是1，同时因为加上第一个最优解，值变小了，所以就不需要第一个最优了。  
第三个最优是1加-3等于-2。大于-3。所以最优是-2。保存第二个数  
第四个最优是4，之前的和没有第四个数大，所以都不要了。  
第五个最优是3，所以保存最优。  
第六个最优是5，保存最优  
依次类推到n…  
我的理解大概就是这样，很细碎，有不足的地方，大家帮我补充一下，感谢！

class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
    #        判断边界
            if len(nums)==0:
                return 0
    #         定义一个表格进行存储上一个子问题的最优解
            d=[]
            d.append(nums[0])    #第一个最优解为第一个元素
            max_=nums[0]      #返回的最大值
            for i in range(1,len(nums)):
                if nums[i]>nums[i]+d[i-1]:
                    d.append(nums[i])
                else:
                    d.append(nums[i]+d[i-1])
                if max_<d[i]:
                    max_=d[i]
            return max_

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220216/db7f77aec94c498f834a0d8070f875b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: /images/20220216/93947c22e5df4ad38923035bb3671dc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]: /images/20220216/ae88a9fbba7c4e21bc787fb7bf2463cf.png