Hello everyone, I have been having a lot of problem in solving this question and I have been looking for any help.
https://codeforces.com/contest/505/problem/C This is the question. Can you please help me find the recurrence relation? If you will read the editorial you will find that they have used relation: dp [ i ][ j ] = (the number of the gems on island i ) + max( dp [ i + j — 1][ j — 1], dp [i + j ][ j ], dp [ i + j + 1][ j + 1]), if i < m , j ≥ 2 but in recurrence relation we used to find out the previous state on (right hand side of the equation because that is how we solve sub-problems ) but here they have related dp[i][j] (current state ) with the state that will be achieved afterwards in the process that is dp[i+j+1][j+1], dp[i+j][j] and dp[i+j-1][j-1]. How are we solving sub-problems here? Can you please help me?
this is an ac solution watch these relations and see if you understamd these relations. yeah we can only modify the past relations but see in this problem , dp[j][i+j] , dp[j+1][i+j+1] and are modified at every step so while taking max we should also consider them also with dp[j][i].
int ans = -1199999 for(int i = 0; i < 32000; i++){ for(int j = max(1, d-250); j < d+250; j++){ dp[j][i] += a[i]; int v = dp[j][i]; ans = max(ans, v); dp[j][i+j] = max(dp[j][i+j], v); dp[j+1][i+j+1] = max(dp[j+1][i+j+1], v); dp[j-1][i+j-1] = max(dp[j-1][i+j-1], v); } } hope it helps