社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

每日一道算法题--leetcode 198--打家劫舍--python

杉杉不要bug • 6 年前 • 557 次点击  
阅读 19

每日一道算法题--leetcode 198--打家劫舍--python

【题目描述】

【代码思路】

一维动态规划,最主要的是找到状态转移方程以及初始状态。状态转移方程是,要么去前一家,要么去前两家和这一家,取其中的较大值。

【上代码】

class Solution:
    def rob(self, nums: List[int]) -> int:
        if(len(nums)==0): return 0
        if (len(nums)==1):return nums[0]
        dp=[]
        dp.append(nums[0])
        dp.append(max(nums[0],nums[1]))
        for i in range(2,len(nums)):
            dp.append(max(nums[i]+dp[i-2],dp[i-1]))
        return dp[len(nums)-1]
复制代码

看效果,线性级别时间复杂度

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/33635
 
557 次点击