Well, false hope...

Because sz can be larger than T.size(), and since T.size() is an unsigned int it will overflow when doing the subtraction.

idk why, but got ac if replace map with unordered_map

You are confusing DP states with DP values. You are also confusing current earned money with the left over money. I've added more intuition for this DP solution on CF Step

I have the same doubt I do not see how we can simply choose the less number of actions over more number of actions when we have money left under consideration too.

What is the guarantee that this local optimization reflects globally as well.

I think this is the same confusion I had when I was doing the VC. I worked on a proof to understand why I had this misconception.

Take a scenario where you are moving to cell (i, j) from previous cells (i, j — 1) and (i — 1, j) with the same pmax value. And suppose the pmax doesn't change at cell (i, j). These represent dp state transitions from (i, j — 1, pmax), (i — 1, j, pmax) -> (i, j, pmax).

Suppose you have the following possible values for state (i, j, pmax), (a, x), where a = number of actions taken, x = leftover money. Now consider two competing values for the state (i, j, pmax) => (a, 0), (a + 1, pmax — 1). Note that the x is constrained because you only take what you need so leftover will always be x mod(pmax). If there is ever going to be a case where you'd take a value with more action because it has more leftover money this would certainly be it.

• Consider if you transition to another adjacent cell (right or down) from both these values. Let's say the cost to transition is c.

1) (a, 0) so to transition from the value (a, 0), you will need to spend some action on accumulating c money. so you will do it need this many more actions m = ceil(c / pmax), and you will be left with some left over money from the remainder of c divided by pmax. so (a, 0) -> (a + m + 1, c mod(pmax))

example, cost = 10, pmax = 4, m = 3, and (a, 0) -> (a + 3 + 1, 2)

2) (a + 1, pmax — 1) You will not have to spend as much action right, cause you had more leftover money. But you will still need m = ceil((c — pmax — 1) / pmax), and that will just reduce your number of actions to achieve the cost c by 1. So it just balances out, you spend 1 less action cancels the fact it was 1 more action. The extra money did not really help.

example, cost = 10, pmax = 4, m = 2, because 10 — 3 = 7, and (a + 1, 3) -> (a + 1 + 2 + 1, 1). This is worse then the value above (a + 4, 2) vs (a + 4, 1).

In general, I get a sense that you can only reduce number of actions by 1 by having more left over money. So it will at best be a tie in number of actions, but it will never lead to an output with fewer actions. And that is the reason you can take values with fewer actions regardless of money situation.

I assumed pmax was constant in these transitions. But I believe if you plug in an increasing pmax in the same proof it follows for that as well. This only works because pmax is weakly increasing I realized when I went over this.

Your question is given a dp state = $$$(i, j, pmax)$$$, how to compare two values of (min moves, money earned), say $$$(a, b)$$$ and $$$(a', b')$$$. We can indeed compare them lexicographically, i.e. if $$$a < a'$$$ or $$$(a = a'$$$ and $$$b > b')$$$ set dp(state) = $$$(a, b)$$$.

So why is this optimal? Because when money is needed to make the transition it is as if we can use $$$pmax$$$ not just $$$p[i][j]$$$. This implies that there is no need to bring large money surpluses, you can always use $$$pmax$$$ if needed at a later move, so trade 1 action for $$$pmax$$$ money just enough to make the transition.

Because, you use just enough actions to make the transition, the current money in the dp value is such that $$$b < pmax$$$ (if it were not the case we could do $$$a -= 1$$$, $$$b -= pmax$$$). So this actually implies that you can lexicographically compare the dp values has I stated before.

Your scenario of having $$$a < a'$$$ and $$$b «< b'$$$ does not occur, as from state $$$(a, b)$$$ you can reach $$$(a + 1, b + pmax)$$$ and as argued $$$b + pmax > b'$$$.

Hello I have put some thoughts after reading the replies in this comment section (Very helpful replies and I am very grateful to them)

This is my proof.

Claim:- The leftover money at any point in time is < pmax. This is the max over all P(i, j) from 1,1 till i, j

Proof:- Let's assume leftover money is x and assume that we are updating dp for i + 1, j. The same can be done i, j + 1.

So, if we directly took modulo with Pmax we would have (R(i, j) $$$-$$$ x) mod Pmax as the remainder. let's name it REM. Now we would have Pmax $$$-$$$ REM leftover money, always < Pmax.
or
x >= R(i, j) then trivially x $$$-$$$ R(i, j) < Pmax.

The claim is proven. Suppose we had two (action, money leftover) pairs for i + 1, j. Let's take the worst possible case.

A, 0
A + 1, Pmax $$$-$$$ 1.

We can see that with just 1 operation we can go from A, 0 to A + 1, Pmax. So taking the lower action count pair is always optimal.

I have only made a more verbose comment over existing replies. It's just a more wordy version of the proof people already mentioned. Thanks once again!

dp[k — 1] + 1 is overflowing intilize dp with some max value say 1e5 and the change last condition (== INT_MAX) to (> n) after doing this 53 / 58 test pass link

Use dp, want the min yen to reach the state (bag index, index of matched prefix of T)