題目：

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()