大厂真题 笔记点赞
题目
队长写了n篇笔记,编号从1-n,每个笔记都有对应的点赞数,队长要找到在着n篇笔记的最大点赞数,但是必须满足以下要求:
相邻两个笔记不能同时选取
问能够取到的最大赞和对应的要选取几个笔记
输入
第一行为几篇笔记
第二行为各自笔记的点赞数
第三行为输出 第一列为最大点赞总数 第二列为选取笔记数目
示例 1:
输入
4
1 2 3 1
输出
4 2
点赞数最大为4,最多选取的笔记总数为2
这道题目主要考察的知识点为动态规划
动态规划主要就是要找准它的转移方程和base case以及目标
转移方程方面 我们看到输出为最多点赞和笔记
我们新建一个数组为dp[i][j]
i代表第i篇笔记
j代表选取的笔记为j
举个例子 dp[5][2] 意思为遍历到第五个笔记的时候如果这个时候我能取两个笔记时候 能取到的点赞数为dp[5][2]
步骤:
我们先开辟个数组dp[N+1][N+1] 数值初始化都为0
base case:
dp[1][1]=nums[0]
转移方程
dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+nums[i-1])
当前遍历到第i个状态的时候
当前如果要选这个笔记,那么要取到i-2篇的时候且选择j-1个笔记的状态加上当前笔记的点赞数
如果不选当前这个笔记,那么直接取i-1篇的时候选择j个笔记的情况
JAVA
-
import java.util.*;
-
pu
文章来源: blog.csdn.net,作者:网奇,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/jacke121/article/details/116246065
- 点赞
- 收藏
- 关注作者
评论(0)