96. Unique Binary Search Trees
发布时间:2020-12-14 03:45:41 所属栏目:大数据 来源:网络整理
导读:https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i) ? ? ? 1 // 用dp[]做cache 否则会超过time limit 2 class Solution { 3 int [] dp; 4 public int numTrees( int
https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i) ? ? ? 1 //用dp[]做cache 否则会超过time limit 2 class Solution { 3 int[] dp; 4 public int numTrees(int n) { 5 dp = new int[n]; 6 return helper(1,n); 7 8 } 9 10 public int helper(int lo,int hi) { 11 if(lo >= hi) return 1; 12 int res = 0; 13 if(dp[hi - lo] != 0) return dp[hi - lo]; 14 for(int i = lo; i <= hi; i++) { 15 res += helper(lo,i-1) * helper(i+1,hi); 16 17 } 18 dp[hi - lo] = res; 19 return res; 20 } 21 } 22 23 24 //神奇的math 25 class Solution { 26 public int numTrees(int n) { 27 int[] res = new int[n+1]; 28 res[0] = 1; 29 res[1] = 1; 30 for(int i = 2; i <= n; i++) { 31 for(int j = 0; j <= i; j++) { 32 res[i] = res[j - 1] * res[i - j]; 33 } 34 } 35 return res[n]; 36 37 } 38 39 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |