# Optimised Java DP solution

• I found many people used double for loops in their DP solution, in which the second iteration j goes from 0 to i.

``````public int numTrees(int n) {

if (n <= 0) return 0;
if (n == 1) return 1;

// dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
// i: 0 --> n - 1; j: n - 1 - i
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i < dp.length; i ++) {
for (int j = 0; j <= i - 1; j ++)
dp[i] += dp[j] * dp[(i - 1) - j];
}

return dp[n];
}
``````

However, according to the symmetric properties of BST, dp[i]*dp[j] = dp[j]*dp[i], for example, dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = dp[0] * dp[2] * 2 + dp[1]*dp[1]. Therefore, we can further optimise the DP solution:

``````public int numTrees(int n) {

if (n <= 0) return 0;
if (n == 1) return 1;

// dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
// i: 0 --> n - 1; j: n - 1 - i

int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;

/*
for (int i = 2; i < dp.length; i ++) {
for (int j = 0; j <= i - 1; j ++)
dp[i] += dp[j] * dp[(i - 1) - j];
}
*/

// further optimise : only caculate half (using the symmetric property of BST)
for (int i = 2; i < dp.length; i ++) {
int j = 0;
for (; j < (i - 1) / 2; j ++)
dp[i] += dp[j] * dp[(i - 1) - j] * 2;
int temp = dp[j] * dp[(i - 1) - j];
dp[i] += (j == i - 1 - j) ? temp : temp * 2;
}

return dp[n];
}
``````

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