最长上坡路线

怎样从“你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？”推导出 跳平台游戏 · 基础 DP，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。

给定一个无序的整数数组，找到其中最长上升子序列的长度。

在本站主例中，你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？

算法最终需要得到或观察：最长上坡路线长度 = 4（2→5→7→101 或 2→5→7→18）。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 表、当前平台 i、扫描前驱 j。
3. 3转移每一步按照 dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。
4. 4收尾读取 最长上坡路线长度 = 4（2→5→7→101 或 2→5→7→18）。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 表、当前平台 i、扫描前驱 j。

给定一个整数序列，求其中的最长上升子序列的长度。这一题就是经典的最长上升子序列的问题。 `dp[i]` 代表为第 i 个数字为结尾的最长上升子序列的长度。换种表述，dp[i] 代表 [0,i] 范围内，选择数字 nums[i] 可以获得的最长上升子序列的长度。状态转移方程为 `dp[i] = max( 1 + dp[j]) ，其中 j nums[i]`，取所有满足条件的最大值。时间复杂度 O(n^2) 这道题还有一种更快的解法。考虑这样一个问题，我们是否能用一个数组，记录上升子序列的最末尾的一个数字呢？如果这个数字越小，那么这个子序列往后面添加数字的几率就越大，那么就越可能成为最长的上升子序列。举个例子：nums = [4,5,6,3]，它的所有的上升子序列为

``` len = 1 : [4], [5], [6], [3] => tails[0] = 3 len = 2 : [4, 5], [5, 6] => tails[1] = 5 len = 3 : [4, 5, 6] => tails[2] = 6 ``` 其中 `tails[i]` 中存储的是所有长度为 i + 1 的上升子序列中末尾最小的值。也很容易证明 `tails` 数组里面的值一定是递增的(因为我们用末尾的数字描述最长递增子序列)。既然 tails 是有序的，我们就可以用二分查找的方法去更新这个 tail 数组里面的值。更新策略如下：(1). 如果 x 比所有的 tails 元素都要大，那么就直接放在末尾，并且 tails 数组长度加一；(2). 如果 `tails[i-1] < x <= tails[i]`，则更新 tails[i]，因为 x 更小，更能获得最长上升子序列。最终 tails 数组的长度即为最长的上升子序列。这种做法的时间复杂度 O(n log n)。

dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。

执行过程中持续维护：dp 表、当前平台 i、扫描前驱 j。

正确性依赖以下不变量：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 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？ 因为：dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。
2. 2平台 9 处理完成，dp[1] = 1ans = max(ans, dp[i])。 因为：答案取全局最大 dp。
3. 3可以接：2 → 5只有更低的前驱才能接。 因为：j < i 保证只往右走。
4. 4平台 3 处理完成，dp[4] = 2ans = max(ans, dp[i])。 因为：答案取全局最大 dp。
5. 5可以接：3 → 7只有更低的前驱才能接。 因为：j < i 保证只往右走。
6. 6可以接：3 → 101只有更低的前驱才能接。 因为：j < i 保证只往右走。
7. 7可以接：2 → 18只有更低的前驱才能接。 因为：j < i 保证只往右走。
8. 8收尾与复杂度最长上坡路线长度 = 4（2→5→7→101 或 2→5→7→18）。 因为：时间 O(n²) · 空间 O(n)。dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "sort"

// 解法一 O(n^2) DP
func lengthOfLIS(nums []int) int {
	dp, res := make([]int, len(nums)+1), 0
	dp[0] = 0
	for i := 1; i <= len(nums); i++ {
		for j := 1; j < i; j++ {
			if nums[j-1] < nums[i-1] {
				dp[i] = max(dp[i], dp[j])
			}
		}
		dp[i] = dp[i] + 1
		res = max(res, dp[i])
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 O(n log n) DP
func lengthOfLIS1(nums []int) int {
	dp := []int{}
	for _, num := range nums {
		i := sort.SearchInts(dp, num)
		if i == len(dp) {
			dp = append(dp, num)
		} else {
			dp[i] = num
		}
	}
	return len(dp)
}

func main() {
    // 1. 主例
    //    输入：mode="lis", nums=[10,9,2,5,3,7,101,18]
    //    期望：最长上坡路线长度 = 4（2→5→7→101 或 2→5→7→18）。
    //
    // 2. 失败 / 未命中
    //    检查：答案取 max(dp)，不是 dp[n-1]。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC674 连续递增；LC354 俄包
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意你面前有一排数字平台。你可以从左往右跳，可以跳过平台，但不能回头。每次只能跳到更高的平台。问题是：最长能连续跳几个平台？
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化dp[i]=停在第 i 个平台时的最长上坡路线长度；从所有更低的前驱里选路线最长的那个。
4. 4证明dp[i]=max(dp[j]+1)，其中 j<i 且 nums[j]<nums[i]。
5. 5复杂度时间 O(n²)，空间 O(n)