- class Solution:
- def rob(self, nums: List[int]) -> int:
- l=len(nums)
- dp=[0]*l
- dp[0]=nums[0]
- if l==1:
- return dp[0]
- dp[1]=nums[1]
- for i in range(2,l):
- dp[i]=max(dp[i-2]+nums[i],dp[i-3]+nums[i])
- return max(dp)
注意数组只有一个数的情况
- class Solution:
- def numSquares(self, n: int) -> int:
- a=[i*i for i in range(int(sqrt(n)+1))]
- dp=[1000000]*(n+1)
- dp[0]=0
- for i in range(1,n+1):
- for l in a:
- if i>=l:
- dp[i]=min(dp[i],dp[i-l]+1)
- return dp[n]
不能用贪心