Unoptimised Recursive Algorithms can repeat calculations on the same data. We can easily get an **exponentially growing number of recursive computations** as the input size grows, which we optimise with DP.

The idea behind Dynamic Programming is to increase the efficiency of fundamentally recursive problems through **caching** of data. Dynamic Programming flips the problem from a top-down recursive solution to a bottom-up solution using **tabulation**. We avoid repeating expensive calculations and can sometimes also improve space efficiency *without a recursive call stack*.

We can implement top-down DP through a different caching technique called **memoization**, but we sacrifice **space efficiency** because we still have a recursive solution. I focus on tabulation here for optimal space efficiency.

There are many posts out there for how DP improves exponential Recursive algorithms to linear complexity. I focus in this post on a rare case where a **recursive solution is more efficient than DP**.

Given a string s, return the longest palindromic substring in s.

```
/* Example Functionality:
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
*/
```

Given a string, represented as `var input: [Character]`

, build a `var table`

of size `input.count`

by `input.count`

, so that `table[i][j] == 1`

if the substring starting from `input[i]`

of length `j + 1`

is a palindrome, and `table[i][j] == 0`

if the substring is not a palindrome.

To calculate `table[i][j]`

, check the value of `table[i+1][j-1]`

, if the value is `true`

and `str[i]`

is same as `str[j]`

, then we make `table[i][j]`

true.

Build the table bottom up with a palindrome detector that detects all the lower length palindromes first. Use the table to build the higher length palindrome. Cache the longest palindrome found so far during this enumeration.

Return the longest length palindrome after iterating through all substrings.

```
func longestPalindromeDP(_ st: String) -> String {
let n = st.count
var st = Array(st)
// Palindrome table initialised to no palindromes.
var table: [[Bool]] = Array(repeating: Array(repeating: false, count: st.count), count: st.count)
// All single character strings are valid palindromes.
var maxLength = 1
var i = 0
while (i < n) {
table[i][i] = true
i += 1
}
// check for sub-string of length 2.
var start = 0
i = 0
while i < n - 1 {
if (st[i] == st[i + 1]) {
table[i][i + 1] = true
start = i
maxLength = 2
}
i = i + 1
}
// Check for lengths greater than 2.
// k is length of substring
var k = 3
while k <= n {
// Fix the starting index
i = 0
while i < (n - k + 1) {
// Get the ending index of
// substring from starting
// index i and length k
let j = i + k - 1
// checking for sub-string from
// ith index to jth index iff
// st[i + 1] to st[(j-1)] is a
// palindrome
if table[i + 1][j - 1], st[i] == st[j] {
table[i][j] = true
if (k > maxLength) {
start = i
maxLength = k
}
}
i = i + 1
}
k = k + 1
}
return String(Array(st[start ..< (start + maxLength)]))
}
```

**NOTE**: This solution is adapted into Swift from GeeksForGeeks.

**Time**: `O(n^2)`

**Space**: `O(n^2)`

We use `O(n^2)`

space complexity to cache the results in a table.

Note that `n^2`

time complexity is more optimal than the `n^3`

Brute Force solution. However, the space complexity is still suboptimal.

Build palindromes from the innermost characters outwards for each possible midpoint. Consider palindromes with an even and with an odd number of characters separately.

Using this traversal technique, we don't need to cache data because we don't repeat calculations and we only need to track the longest palindrome found thus far.

```
func helper(_ input: inout [Character], _ idx: Int, _ result: inout String) {
// Edge case
if input.isEmpty {
return
}
// Terminate recursion
if idx == input.count {
return
}
// Build palindromes
var left = idx
var right = idx + 1
var palindrome = String(input[idx])
while left >= 0, right < input.count {
if input[left] == input[right] {
palindrome = String(input[left...right])
} else {
break
}
left -= 1
right += 1
}
left = idx - 1
right = idx + 1
var palindromeTwo = String(input[idx])
while left >= 0, right < input.count {
if input[left] == input[right] {
palindromeTwo = String(input[left...right])
} else {
break
}
left -= 1
right += 1
}
if palindromeTwo.count > palindrome.count {
palindrome = palindromeTwo
}
if palindrome.count > result.count {
result = palindrome
}
}
func longestPalindrome(_ input: String) -> String {
var result: String = ""
var input = Array(input)
for i in 0 ..< input.count {
helper(&input, i, &result)
}
return result
}
```

**NOTE:** I independently developed this algorithm without referencing GeeksForGeeks.

**Time**: `O(n^2)`

**Space**: `O(1)`

We only use `O(1)`

space complexity because the method call stack gets reset to size 0 when invoking every additional `helper(..)`

call.

**Dynamic Programming** is a powerful technique to optimise combinatorial enumeration time complexity for many problems, but **may not always produce the most optimal solution**.

In this post, I outline a recursive solution that didn't require caching and thus improved the space complexity of the DP solution. This is counterintuitive because the traditional recursion solution is optimised with DP.

So we can see that coming up with the right overall solution strategy can optimize the efficiency of DP solutions. Don't *always* assume DP is the best solution.