LC300
最长上坡路线
跳平台游戏 · 基础 DP可视化:动态规划表你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？
可以跳过平台，但不能回头；只能跳到更高的平台。
基础 DP 时间 O(n²)基础 DP 空间 O(n)进阶二分 O(n log n) / O(n)
题目1 / 61
题目与输入建立输入、目标与算法心智
正在加载上坡路线...
当前发生了什么
你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？
机器状态
dp 表、当前平台 i、扫描前驱 j。
为什么正确
dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。
不变量
dp[i]=max(dp[j]+1)，其中 j<i 且 nums[j]<nums[i]。
面试怎么说
基础 O(n²) DP：dp[i] 表示以 i 结尾的 LIS；进阶 O(n log n) 用 tails 数组。
人类输入
你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？
机制
dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。
机器状态
dp 表、当前平台 i、扫描前驱 j。
可观察结果
最长上坡路线长度 = 4（2→5→7→101 或 2→5→7→18）。
不变量
- · dp[i]=max(dp[j]+1)，其中 j<i 且 nums[j]<nums[i]。
常见误区
- · 答案取 max(dp)，不是 dp[n-1]。
- · 进阶牌堆法 O(n log n) 见页面折叠区，tails 不一定是真实路线。
迁移练习
- · LC674 连续递增
- · LC354 俄包
面试怎么答
基础 O(n²) DP：dp[i] 表示以 i 结尾的 LIS；进阶 O(n log n) 用 tails 数组。