Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.

Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).

Unique Binary Search Trees

S

i find in widows you should initialize Array,otherwise, you may get the result is the addres of array add some number. correct answer:

K

@cuichenxuan said in Dp problem. 10+ lines with comments:

hy dp[0] = dp[1] = 1? thank you!

F(n) = F(0) * F(n-1) + F(1) * F(n-2) + F(2) * F(n-3) + ... + F(n-2) * F(1) + F(n-1) * F(0)

Consider the formula above. Have you notice that there are expressions F(0)*F(n-1) and F(n-1)*F(0) ? If you set F(0) as 0 then F(n-1) will be cancelled out. We need to keep the F(n-1), so , We have to set F(0) as 1. bbe like that

I prefer to the crystal explanation!

@StefanPochmann why not doing this :

G

@mani89 It hadn't click on me until I read your answer. Thank you!

L

You are such a talent! What a cool solution!

A

Thanks! Here is another good one: https://www.youtube.com/watch?v=YDf982Lb84o

No one has replied

Y

share my similar solution.

E

arr is the array storing previously computed results. That is, arr[3] is the number of trees when n=3. Therefore,

means we simply return the stored result if it is already computed.

@dragonmigo, the most clear explanation I've seen, thanks!

R

@Irving_cl thanks bro!!! got it...

exactly, we don't need sum anywhere

H

This solution is likely to get TLE.

T

Since the result is int: n cannot be bigger than 19, so long instead of double would suffice:

Disabled Categories are greyed out

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.