Pudding and Coins

Note we need to count permutations such that $\min(1, p_1)+\min(2, p_2) + \cdots + \min(n, p_n)=s$

We formulate a dp solution. Assume we are iterating over positions $1, 2, \cdots, n$ and while iterating, we can keep positions empty or fill them with some non-larger value and we can put current value in already iterated positions or leave them unassigned for now. Thus we can define $dp[n][o][s]$ to mean number of prefixes $1, 2, \cdots, n$ with $o$ positions unfilled (and thus $o$ numbers unassigned) and $s$ confirmed sum. Then when at position $i$, five things can happen

1. We can put $i$ at position $i$

2. We can put $i$ at an earlier unfilled position and leave position $i$unfilled

3. We can put $i$ at an earlier unfilled position and put some earlier unassigned value at position $i$

4. We can leave $i$ unassigned and position $i$ unfilled

5. We can leave $i$ unassigned and put an earlier unassigned value at position $i$B

By considering this cases we can come up with transitions. Note contribution to sum are confirmed in case 1 or when a position is left unfilled for future or when a value is left unassigned for future.