Hello codeforces! I have a question about a DP problem:

Giving table $$$n * m$$$, each cell has value from $$$-10^9$$$ to $$$10^9$$$, you are standing at a cell in column $$$1$$$ and you must go to a cell in column $$$m$$$. For each step, if you stand at cell $$$(i, j)$$$, you can go to cell $$$(i-1, j+1), (i, j+1), (i+1, j+1)$$$. Moreover, you have $$$k$$$ special moves can be described as if you stand at cell $$$(i, j)$$$, you can go to $$$(r, j)$$$ or $$$(i, c)$$$ which $$$r \neq i, c \neq j$$$. You don't have to use all $$$k$$$ special moves and for each step, the next cell you go must different from the current cell you standing. Find maximun sum.

constraint:

• $$$n, m \leq 2207$$$
• $$$k \leq 10$$$

I have a code which $$$O(n * m * k)$$$ but when I submitted, I got TLE. (this is link to the code). I have stucked this problem for 2 days @-@. Please help!