rahul1995's blog

By rahul1995, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I know you said not to say this but the answer is mostly going to be just: Practice!

CP Experience isn't just about time, you registered 6 years ago but only took part in 35 contests and solved only around 108 problems... I know people who registered < a year and solved around 700-800 problems already.

Practice makes perfect.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use Codechef more. Please check I have same handle there.