Dynamic programming

Question 1

Longest increasing subsequence

Answer 1

1. each number is longest increasing subsequence of value 1.
2. So for each index, iterate from the start and keep on check whether any value lesser than the current value
3. If so, max(dp[prev], maxLen)
4. Finally update dp[i] = maxLen + 1
5. maxAnswer = max(maxAnswer, dp[i])

Question 2

Perfect square

Answer 2

1. Find the square required by doing sqrt(n)
2. For each index, iterate over each sqr and check if its lesser and equal to the index
3. If so dp[i] = min(dp[i], dp[i - j*j] + 1)