Hello, I have always found it difficult to come up with a better DP solution with lesser states or lesser operations to do to fill each DP state. I don't know if you guys have been in the same situation where you can come up with some recurrence relation but still to avoid TLE or memory constraints, you have to think DP states in different way.

For e.g.: Please read this question and the solution given: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/solution/

My approach v/s Approach 1 of this solution

So I thought of DP state dp[i][j] = max profit till i-th day using j transactions. where i <= n and j <= k

dp[i][j] = max(dp[i-x][j-1] + profit gained (if possible) by buying on (i-x)th day and selling on i-th day) for x = 1 to i i.e., I try buying at some (i-x)th day and sell it on i-th day hence calculating each state will take i operations. So overall time complexity = O(n*k*n)

Whereas, in Approach 1 of Solution given, states are defined differently and they solve it in O(n*k) only.

Could someone please help me? I don't know if this is a right question I am asking, because I think you guys would say I will only have to do practice. But I am doing CP for 6 years so I am clueless right now.