中文简洁网站设计图,软件开发专业探索,做长图文网站,秦皇岛旅游攻略题目#xff1a;
HJ103 Redraiment的走法
题解#xff1a;
dfs 暴力搜索
枚举数组元素#xff0c;作为起点如果后续节点大于当前节点#xff0c;继续向后搜索记录每个起点的结果#xff0c;求出最大值 public int getLongestSub(int[] arr) {int max 0;for (int i 0…题目
HJ103 Redraiment的走法
题解
dfs 暴力搜索
枚举数组元素作为起点如果后续节点大于当前节点继续向后搜索记录每个起点的结果求出最大值 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 start1; 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()
