type
status
date
slug
summary
tags
category
icon
password
这次刷一道dp题,加强下思维,做了一会，直接打开官方题解研究，参考代码
📝 主旨内容
这题的意思是，给定n个数，任意两个数之间的差不为k，最多可以选出多少个数。
如果k=0的话，只需要找到不相同的数就行
这里使用set
如果k≠0，就需要使用动态规划了
首先要知道这里用动态规划表示的意思：即dp[i]中每一个下标表示可以上线的用户,也就是符合条件的数的个数
这时他的转换方程就是应该是递增的i
首先dp[i]有效，所以i-k就不能用，但是可以用i-2*k,而且初始化的时候已经把dp[i]存入了这个数的个数,所以dp[i]=dp[i-2*k]+dp[i]
其次是dp[i]无效,所以i-k就可以直接用dp[i]=dp[i-k]
得出转换方程：
dp[i]=max(dp[i-2*k]+dp[i],dp[i-k]);
dp[i]=max(dp[i-2*k]+dp[i],dp[i-k]);
🤗 最终代码（来源蓝桥官方题解)
有关题目或文章的问题，欢迎您在底部评论区留言，一起交流~
- Author:小彦同学
- URL:https://alicization.site/article/2024/03/21/2b6dc178-c1c0-4196-8119-202fac0ec73d
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
