codes-bank's People
codes-bank's Issues
lc740 Delete and Earn
740.Delete and Earn
总结:
- 找到dp[i], dp[i-1], dp[i-2] 之间的关系
核心思路:
Once you store the frequency of each number, you can easily see that it is like the 198.House Robber problem:
1.dp的定义
dp[i]
代表到第 i 个位置的时候,最大值是多少:
2.转移方程
-
如果相邻,那就和house robber 一模一样
if temp[i]-temp[i-1]==1:
dp[i]=max(dp[i-1], temp[i]*frequency[temp[i]] + dp[i-2])
如果不相邻:那就可以直接加上去else:
dp[i]=dp[i-1]+temp[i]*frequency[temp[i]]
3.初始化
dp[0] = nums[0]*frequency[nums[0]]
if temp[1]-temp[0]==1: dp[1]=max(dp[0], temp[1]*frequency[temp[1]]) else: dp[1]=dp[0]+temp[1]*frequency[temp[1]]
class Solution:
# 输入nums = [2,2,3,3,3,4]
def deleteAndEarn(self, nums: List[int]) -> int:
frequency = collections.Counter(nums)
# frequency = Counter({3: 3, 2: 2, 4: 1})
n = len(visited)
if n==1:
return nums[0]*frequency[nums[0]]
dp = [0]*n
temp = list(frequency.keys()) # 把所有的元素单独列出来:[2, 3, 4]
temp.sort()
dp[0] = temp[0]*frequency[temp[0]]
if temp[1]-temp[0]==1:
dp[1]=max(dp[0], temp[1]*frequency[temp[1]])
else:
dp[1]=dp[0]+temp[1]*frequency[temp[1]]
if n==2:
return dp[1]
for i in range(2,n):
if temp[i]-temp[i-1]==1:
dp[i]=max(dp[i-1], temp[i]*frequency[temp[i]] + dp[i-2])
else:
dp[i]=dp[i-1]+temp[i]*frequency[temp[i]]
return dp[n-1]
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.