題目

https://leetcode.com/problems/maximum-length-of-pair-chain/description/

題解

暴力遞歸->傻緩存->dp

寫完之后，看了答案發現，是我想復雜了。。

就當練了下 dp 吧。

class Solution {int n;int min, max;int offset;public int findLongestChain(int[][] pairs) {n = pairs.length;Arrays.sort(pairs, (o1, o2) -> {if (o1[0] < o2[0]) return -1;else if (o1[0] > o2[0]) return 1;else return o1[1] - o2[1];});// Approach 1: Recursive, Brute Force // return process1(pairs, 0, Integer.MIN_VALUE);// Approach 2: Recursion with Memoization // min = pairs[0][0]; // offset = -min + 1; // for (int[] p : pairs) { // max = Math.max(max, p[1]); // } // int[][] dp = new int[n + 1][max - min + 2]; // for (int[] a : dp) { // Arrays.fill(a, -1); // } // for (int j = 0; j < dp[0].length; j++) { // dp[n][j] = 0; // } // return process2(pairs, 0, min - 1, dp);// Approach 3: Dynamic Programmingmin = pairs[0][0];offset = -min + 1; // 將[min,max]映射到數組的[0, max-min+1]范圍for (int[] p : pairs) {max = Math.max(max, p[1]);}int[][] dp = new int[n + 1][max - min + 2];for (int[] a : dp) {Arrays.fill(a, -1);}for (int j = 0; j < dp[0].length; j++) {dp[n][j] = 0;}for (int i = n - 1; i >= 0; i--) {for (int j = 0; j < dp[0].length; j++) {int preEnd = j - offset;int p1 = pairs[i][0] > preEnd ? dp[i + 1][pairs[i][1] + offset] + 1 : 0;int p2 = dp[i + 1][j];dp[i][j] = Math.max(p1, p2);}}return dp[0][0];}// public int process1(int[][] pairs, int i, int val) { // 在可選位置為i的情況下，能獲得的最大長度 // if (i == n) return 0; // int p1 = pairs[i][0] > val ? process1(pairs, i + 1, pairs[i][1]) + 1 : 0; // 選當前元素 // int p2 = process1(pairs, i + 1, val); // 不選當前元素 // return Math.max(p1, p2); // } // // public int process2(int[][] pairs, int i, int preEnd, int[][] dp) { // int j = preEnd + offset; // if (dp[i][j] >= 0) return dp[i][j]; // // int p1 = pairs[i][0] > preEnd ? process2(pairs, i + 1, pairs[i][1], dp) + 1 : 0; // int p2 = process2(pairs, i + 1, preEnd, dp); // // dp[i][j] = Math.max(p1, p2); // return dp[i][j]; // } }

總結

以上是生活随笔為你收集整理的leetcode 646. Maximum Length of Pair Chain | 646. 最长数对链（暴力递归-＞傻缓存-＞dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。