Since my previous blog (using dy/dx arrays on grids) seemed to be helpful for some beginners, I wanted to share another very common trick that saves time with dp (and other optimization problems) and is much less error prone than it's counterpart. Again, this is a very minor trick and won't make the difference between solving a problem and missing it, but it's helpful to understand how it works in case you want to try it at some point (many LGMs have this in their templates). Somewhere in your template, start by writing these two functions.

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

We'll talk about ckmin since ckmax does the same thing but with max. Let's say you want to find the number of integers in an array that are smaller than all the integers before it. To solve this in O(n), simply maintain int ans = 0 and int currMin = INF and iterate over the array. Normally you may see something like this:

if(a[i] < currMin){ currMin = a[i]; ans++; }

While this works, the functions I posted above can be used like so:

if(ckmin(currMin, a[i])) ans++;

If you look closely at the implementation of ckmin, it should be clear that these two are identical.

Although it seems like a practically useless detail, using ckmin and ckmax can be much less error prone in more difficult problems and can lead to very clean dp implementations (such as 0-1 knapsack, which I would put here if I knew how formatting code actually works on these blogs).

I hope this makes sense. If I think of more common tricks to explain in the future I'll post about it so keep your eyes open.

• Jellyman