70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
Python
方法1
class Solution:
def climbStairs(self, n: int) -> int:
if n==1 or n==0:
return 1
return self.climbStairs(n-1)+self.climbStairs(n-2)
思路:通过迭代实现统计,但会超出时间限制。
方法2
class Solution:
def climbStairs(self, n: int) -> int:
x_2,x_1,x=0,0,1
for i in range(1,n+1):
x_2=x_1
x_1=x
x=x_1+x_2
return x
思路:动态规划。首先我们可以推导出f(n)=f(n-1)+f(n-2)
,因为到达n阶台阶,只能从第n-1阶和第n-2阶台阶过去。因此对于第i届台阶来说,那么f(i)=f(i-1)+f(i-2)
,因此x_1表示f(i-1),x_2表示f(i-2),x表示f(i)。
GO
func climbStairs(n int) int {
x1,x2:=1,0
//f(n)=f(n-1)+f(n-2),则x1代表f(n-1),x2代表f(n-2)
for i:=1;i<=n;i++{
//i表示楼梯数
x1,x2=x1+x2,x1
//上面表示f(i-1)变为f(i),f(i-2)变为f(i-1)。f(i)=原来的(f(i-1)+f(i-2)),
}
return x1
}
思路:同动态规划,看注释。
198. 打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
Python
方法1
class Solution:
def rob(self, nums: List[int]) -> int:
lenght=len(nums)
if not nums or lenght==0 :
return 0
elif lenght==1:
return nums[0]
dp=[0]*lenght
dp[0]=nums[0]
dp[1]=max(dp[0],nums[1])
for i in range(2,lenght):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]
思路:动态规划,首先dp负责记录当前位置已累计达到最大结果。因此dp[0]
为nums[0]
,dp[1]
要在dp[0]
和nums[1]
直接取最大值(因为nums[0]
和nums[1]
相邻,不能同时取值),在指针到达nums[2]
时,dp[2]
则取(dp[1]
)和(dp[0]+nums[2]
)之间的大值,dp[3]
则取(dp[2]
)和(`dp[1]+nums[3])最大值,同理向后推到,最后一个dp,则是最大值。
方法2
class Solution:
def rob(self, nums: List[int]) -> int:
lenght=len(nums)
if not nums or lenght==0 :
return 0
elif lenght==1:
return nums[0]
first=nums[0]
second=max(first,nums[1])
for i in range(2,lenght):
first,second=second,max(nums[i]+first,second)
return second
思路:思路同上述动态规划,只是进行了空间优化,因为dp每次使用dp[i]
与dp[i-1]
,前面的dp则已无作用,因此可以采用两个变量分别代表dp[i]
与dp[i-1]
,每次只需要向前挪位就可以。因此first代表dp[i-1]
,second代表dp[i]
,每次循环则进行挪位赋值。
GO
func rob(nums []int) int {
lenght:=len(nums)
if lenght==0 || nums==nil{
return 0
}else if lenght==1{
return nums[0]
}
first:=nums[0]
second:=max(first,nums[1])
for i:=2;i<lenght;i++{
first,second=second,max(nums[i]+first,second)
}
return second
}
func max(x,y int) int{
if x>y{
return x
}
return y
}
思路:同python思路。
120. 三角形最小路径和
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
输入:triangle = [[-10]]
输出:-10
Python
方法1
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp=[[0]*len(_) for _ in triangle]#dp原始
length=len(triangle)
dp[0][0]=triangle[0][0]
for i in range(1,length):
dp[i][0]=dp[i-1][0]+triangle[i][0]
for j in range(1,len(triangle[i])-1):
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
dp[i][-1]=dp[i-1][-1]+triangle[i][-1]
return min(dp[-1])
思路:动态规划,这是我一开始的思路,通过创建与triangle大小一样的动态规划数组。当然第一开始我边界问题并没有考虑清楚,看了官网才明白。
首先在一般情况下dp[i][j]
的是在dp[i-1][j-1]
和dp[i-1][j]
找最小值再加上triangle[i][j]
。代码:dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
但在边界上的dpi只有一个来源dpi-1,而dpi只能来源于dpi-1,因此在写代码时要单独写出来。dp[i][0]=dp[i-1][0]+triangle[i][0]
和dp[i][-1]=dp[i-1][-1]+triangle[i][-1]
最后在dp[-1]
中找到最小值就是结果。
方法2
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
length=len(triangle)#dp优化-二维
dp=[[0]*len(triangle[-1]) for _ in range(2)]
dp[0][0]=triangle[0][0]
for i in range(1,length):
curr, prev = i % 2, 1 - i % 2
dp[curr][0]=dp[prev][0]+triangle[i][0]
for j in range(1,i):
dp[curr][j]=min(dp[prev][j-1],dp[prev][j])+triangle[i][j]
dp[curr][i]=dp[prev][i-1]+triangle[i][-1]
return min(dp[(length-1)%2])
思路:同上一题,该题目也能进行优化,我们只需要保留两个列数组即可将完成动态规划,首先是dp[curr]
保存当前,dp[prev]
则是记录的上一行的结果。但dp[curr]和dp[prev]
不是数值,而是list形式,通过挪位赋值虽然可以,但是比较繁杂,因此可以直接通过更换下标形式来更换。每次用curr去覆盖prev数组,而prev则指向旧的curr数组。
方法3
length=len(triangle)#dp优化-一维
dp=[0]*length
dp[0]=triangle[0][0]
for i in range(1,length):
dp[i]=dp[i-1]+triangle[i][i]
for j in range(i-1,0,-1):
dp[j]=min(dp[j-1],dp[j])+triangle[i][j]
dp[0]+=triangle[i][0]
return min(dp)
思路:同上,二维的也可以进行优化成一维。优化思路,通过创建一个长度为len(triangle)的数组(及最后一行的长度),分析代码我们可以看出for j in range(i-1,0,-1)
与之前不同,为什么?
因为只有各个数组如果和之前for j in range(1,len(triangle[i])-1)
一样,则会出现dp[j-1]
被更新,但dp[j]
取dp[j]
和dp[j-1]
直接小的与triangle[i][j]
相加,但是dp[j-1]
已经被更新,则出现错误,那么如何避免这种情况发生?
则是采用倒序,倒叙dp[j]
是与dp[j]
与dp[j-1]
取小与triangle[i][j]
相加,虽然dp[j]
被更新,但在dp[j-1]
更新时取的时dp[j-2]
和dp[j-1]
进行的取消,与dp[j]
无关,则不影响结果。
方法4
length=len(triangle)-1
dp=[_ for _ in triangle[-1]]
for i in range(length-1,-1,-1):
for j in range(i+1):
dp[j]=min(dp[j],dp[j+1])+triangle[i][j]
return dp[0]
思路:还有没有更便捷的方法呐。答案有,整体倒序,我从三角形的底部出发,从顶部出来。顶部只有一个则出口肯定是dp[0]
,其余思路都同上面一维方法,只是简化了最后一步的取min。为什么这里的不用取倒序for j in range(i+1)
,原因第一,不用考虑边界问题,每一个都会有两个入口存在,因此不会出现j-1而是j+1,第二,dp[j]
的更新不会影响到dp[j+1]
的入口判断(入口dp[j+1]
和dp[j+2]
)。
GO
func minimumTotal(triangle [][]int) int {
length:=len(triangle)
dp:=make([]int,0,length)
dp=append(dp,triangle[length-1]...)
for i:=length-2;i>=0;i--{
for j:=0;j<=i;j++{
if dp[j]>dp[j+1]{
dp[j]=dp[j+1]+triangle[i][j]
}else{
dp[j]=dp[j]+triangle[i][j]
}
}
}
return dp[0]
}
思路:同python最后一个