Lates_'s blog

By Lates_, history, 4 months ago, In English

I posted it for a translation by Google.

We have base cases

DP[i][0]=0 DP[i][i]=k⋅i And transition DP[i][j]=(DP[i−1][j−1]+DP[i−1][j])/2 Check the explanation for the easy version to see why.

This DP can be optimized by looking at contributions from the base cases.

If we draw the DP states on a grid and ignore the division by 2 in the transition, we can see that the number of times states DP[i][i] contributes to state DP[n][m] is the number of paths from (i,j) to (n,m) in the grid such that at each step, both i and j increase, or only j increases, except we have to exclude paths that go through other base cases. The number of such paths is (n−i−1m−j). Since the number of steps in all of these paths is the same, we can account for the division by 2 in each transition by dividing by 2n−i in the end.

To find the value of DP[n][m] we sum the contribution form every base case DP[i][i] for 1≤i≤n.

  • Vote: I like it
  • -26
  • Vote: I do not like it

4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

$$$2400$$$ rated problems are too hard for your level imo.

  • »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right. I can't solve it before.