Java教程

编程—小红书面试题 挑选总点赞数最多笔记集合

本文主要是介绍编程—小红书面试题 挑选总点赞数最多笔记集合,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

参考大佬的解法

挑选点赞数最多的不连续编号笔记集合,采用动态规划求解

不连续编号意味着选中nums[i],则不能选择nums[i+1],只能在nums[i+2:]中选择,前面的选择方案直接影响后面的选择,因此采用动态规划求解

dp[i] = x:从 i 开始挑选笔记, 最大点赞数为x

推导过程:从编号i开始挑选时,有以下两种情况:

1. 选择编号i笔记nums[i],意味着nums[i-1]不能选择,此时dp[i]=dp[i-2]+nums[i]

2. 不选择编号i笔记nums[i],此时dp[i]=dp[i-1]

n = int(input())
a = input()
nums = [int(i) for i in a.split(" ")]
dp = [0 for _ in range(n)]
count = [0 for _ in range(n)]
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
count[0] = 1
count[1] = 1
for i in range(2,n):
    if dp[i-2]+nums[i]>dp[i-1]:  # 选择
        dp[i]=dp[i-2]+nums[i]
        count[i] = count[i-2]+1
    else:  # 不选择
        dp[i]=dp[i-1]
        count[i] = count[i-1]
print(dp[n-1],count[n-1])

这篇关于编程—小红书面试题 挑选总点赞数最多笔记集合的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!