题目：

HJ103 Redraiment的走法

题解：

dfs 暴力搜索

1. 枚举数组元素，作为起点
2. 如果后续节点大于当前节点，继续向后搜索
3. 记录每个起点的结果，求出最大值

    public int getLongestSub(int[] arr) {int max = 0;for (int i = 0; i < arr.length; i++) {int number = dfsForGetLongestSub(arr, i);max = Math.max(max, number);}return max;}public int dfsForGetLongestSub(int[] arr, int start) {if (start > arr.length) {return 0;}int max = 1;for (int i = start+1; i < arr.length; i++) {if (arr[i] > arr[start]) {max = Math.max(max, dfsForGetLongestSub(arr, i) + 1);}}return max;}

时间复杂度：O()

动态规划

求取最长递增子序列。

设dp[i]表示以i为终点能走的最大步数，当 j < i 时：

• 如果arr[j] < arr[i] 证明可以从 j 跳到 i ，那么dp[i] = dp[j] + 1
• 如果arr[j] >= arr[i] 证明无法从 j 跳到 i ，那么dp[i] = dp[i] 

由此可得dp方程，dp[i] = max(dp[i], dp[j]+1)。

dp方程初始化：如果不能调到任何的桩，那么只能在起点，所以初始化 dp[1-n] = 1。

    public int getLongestSub(int[] arr) {int[] dp = new int[arr.length];int max = 0;Arrays.fill(dp, 1);for (int i = 1; i < arr.length; i++)for (int j = 0; j < i; j++) {if (arr[j] < arr[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);max = Math.max(max, dp[i]);}}return max;}

时间复杂度：O()