LeetCode with Python -> Dynamic Programming
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last, now = 0,0
for i in nums:
last, now= now, max(last+i, now)
return now # redo this later
# n,m = 1,2
# n,m = n+m, n variables on the left side present the original ones
# n==3,m==1
746. Min Cost Climbing Stairs
On a staircase, the i
-th step has some non-negative cost cost[i]
assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost
will have a length in the range[2, 1000]
.- Every
cost[i]
will be an integer in the range[0, 999]
class Solution(object):
def minCostClimbingStairs(self, cost):
"""
:type cost: List[int]
:rtype: int
""" take0,take1 = 0,0
for i in cost:
take0,take1 = take1, min(take0,take1)+i
return min(take0,take1)
# redo later
最新文章
- 移居 GitHub
- js获取浏览器body或窗宽度高度合集
- asp.net identity 2.2.0 在WebForm下的角色启用和基本使用(三)
- 修改 Docker 默认网桥地址
- xml 解析
- [转]Oracle如何实现创建数据库、备份数据库及数据导出导入的一条龙操作
- Application,Session和Cookie
- iOS开发zhiATM机的设计与实现
- TCP/IP笔记(四)IP协议
- [动态规划]P1004 方格取数
- 本地访问服务器上的wamp
- Linux常用命令手册
- [译文]Domain Driven Design Reference(一)—— 前言
- SCOI 2019 划水记
- snap7和plc的IP设置问题
- hdu 4891 模拟水题
- Yahoo数据仓库架构简介
- Winform中用了皮肤控件之后,报错:容量超出了最大容量 参数名:capacity
- 在程序中使用命令行的方式来调用py文件
- 【jdk源码分析】java多线程开启的三种方式