Dynamic Programming21 sections · 916 units
Open in Course

Vocabulary - Tight Bound

The key constraint

The tight bound tracks whether you're still constrained by the upper limit NN. If your first two digits match NN's first two digits exactly, you're "tight" and can't exceed NN's third digit. Example: N=325N = 325. If you've placed 3232, you're tight. Your next digit can only be 00-55.

But if you placed 3131, you're no longer tight. Your next digit can be 00-99. Once you place a digit smaller than NN's corresponding digit, you become "loose" and stay loose forever. You can never exceed NN anymore, so all future digits are free.