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

Nice insight!

In fact, we can make ckmin and ckmax even more general (so we can use them for long long, long double, etc. -- not just int)

Or, if you are not opposed to having macros (and sacrificing the boolean return), even easier:

Can you explain what you mean by sacrificing the boolean return?

With his macros, he can't use those in if statements as shown in the post. The whole idea of it is to use if(ckmin(a,b)) to run code whenever a is actually changed. Using #define ckmin(a,b) a = min(a,b) doesn't do this.

Jellyman102

will also work

BTW, love the blogs, they help a lot! Please make more! :D

I'm already short on ideas but I'll make new ones whenever something comes to mind.