首页 > 试题广场 >

Redraiment的走法

[编程题]Redraiment的走法
  • 热度指数：193391 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？

数据范围：每组数据长度满足 ， 数据大小满足




输入描述:
数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度


输出描述:
输出一个结果
示例1

输入

6
2 5 1 5 4 5

输出

3

说明

6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5 ，下标分别是 1 5 6
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5， 下标分别是 3 5 6
从第5格开始走最多有2步,4 5， 下标分别是 5 6
所以这个结果是3。
算法知识视频讲解
开通博客
头像 君君橙
发表于 2021-03-29 16:13:06
关于初始化 数组 dp 中存储着对应 nums 位置的桩最大次数，所以创建的时候默认为 1，因为当前桩本身就是一步。 关于状态转移方程 其中 nums[j] < nums[i]，即扫描 i 前面的桩，如果有比 i 小的话就使用状态转移方程 dp[i] = max(dp[i], dp[j] + 展开全文
去ta的博客 赞 (63) 回复(4) 收起
头像 牛客8008419号
发表于 2021-12-05 02:54:01
这道题也可以看作“动态规划问题”，建议先看视频（10mins）https://www.bilibili.com/video/BV1AB4y1w7eT （感谢博主如此清晰的解析和制作视频的良苦用心，辛苦了，十分感谢） 举例：数组[1, 5, 2, 4, 3]，求升序排列的子数组最大长度 题解：对于数 展开全文
去ta的博客 赞 (44) 回复(3) 收起
头像 日不落拓海海
发表于 2022-02-18 18:12:38
假设 dp[i]为终点为第i个桩的最大走法 那么比较之前num[j]中比num[i]小的桩的最大走法： 如果 num[j]< num[i],那么就有两种情况： 踩上j桩： dp[i] = 1 + dp[j] 不踩，忽略： dp[i] = dp[i] （原数量不变） 取两个情况的最大值 wh 展开全文
去ta的博客 赞 (31) 回复(0) 收起
头像 牛客286623416号
发表于 2021-09-26 18:10:53
使用lamada表达式将String[]优雅的转为int[]然后遍历运算，存在临时的数组里。对数组排序，结果要加1，因为 5 到5 也视为1步。 import java.util.*; public class Main{ public static void main(String[] 展开全文
去ta的博客 赞 (26) 回复(11) 收起
头像 wh728
发表于 2020-08-07 17:37:56
int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 0); int res = 1; 展开全文
去ta的博客 赞 (23) 回复(1) 收起
头像 代码界的小白
发表于 2021-11-30 17:18:22
题目主要信息 1、多组数据，每组有两行数据，第一行为输入数组的个数，第二行输入数组内容 2、找到可以走的步数最多的步数 方法一：暴力用动态规划 具体做法 看到题目我们可以将其理解为求解最长递增子序列的问题，显然就是dp的问题，dp[i]表示到元素i结尾时，最长的子序列的长度。 如下例子[2 5 1 展开全文
去ta的博客 赞 (20) 回复(4) 收起
头像 虹色萤火虫
发表于 2020-08-29 23:14:38
纯C 动态规划是真的🐂🍺 最长上升子序列的解法 详细说明：leetcode:最长上升子序列的官方解法时间复杂度：O(n^2)空间复杂度：O(n) #include <stdlib.h> #include <stdio.h> int main() { int n; 展开全文
去ta的博客 赞 (17) 回复(2) 收起
头像 摸鱼学大师
发表于 2021-11-02 12:56:32
题目的主要信息： 对于一个数组，从前往后，每次只能从小到大，问最多经过多少数字 即寻找最长递增子序列的长度 方法一：暴力动态规划 具体做法： 要找到最长的递增子序列长度，常用方法是动态规划，dp[i]dp[i]dp[i]表示到元素iii结尾时，最长的子序列的长度，初始化全部为1。 遍历两层，前 展开全文
去ta的博客 赞 (17) 回复(2) 收起
头像 showtimewalker
发表于 2020-07-20 20:10:42
/*首先这个算法不是我想出来的，是看了别人的算法后添加了自己的理解这个题目的解题思路和正常思维不同不是将每个位置视为起点，而是视为终点，求出该位置的最大上升次数再求出所有位置的最大上升次数的最大值*/ include using namespace std; define max(a,b) (a& 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 米斯特rollin
发表于 2022-05-03 18:12:09
题解 改题为求 最长升序子序列问题 1.定义一个数组dp用于存储每个数最长子序列的数值，默认为1(因为一个数的时候他的最长序列为1)。 2.使用两个下标i,j（j<i）计算数组arr 与 对应dp的值；如果arr[i] > arr[j] 的时候；计算dp[i] 此时 dp[i] = Ma 展开全文
去ta的博客 赞 (10) 回复(0) 收起

问题信息

排序
难度：
310条回答 42327浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Redraiment的走法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号