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.