defining the DP state
Every dynamic program rests on one design decision made before any code: what exactly is a subproblem, and how do I name it? The answer is the state — a small bundle of values that pins down one subproblem precisely and that you will use as the key into your table. Choosing it well is most of the work; once the state is right, the recurrence usually falls out, and once it is wrong, no amount of clever coding will save you. Think of the state as the question your table cell answers, written so completely that two different cells can never mean the same thing.
A good state has two properties. It must be sufficient: it captures everything about the situation that affects the future of the optimization, so that the best continuation depends only on the state and not on hidden history. And it should be minimal: it carries no irrelevant detail, because every extra dimension multiplies the number of states and thus the running time. For the 0/1 knapsack you might define dp[i][w] = the best total value achievable using only the first i items with capacity w. That pair (i, w) is sufficient — given it, future choices do not care which specific earlier items you took, only how much capacity remains — and it is minimal, since dropping either coordinate would make different situations collide.
The number of distinct states, multiplied by the work to compute one of them, is the running time, so state design is where the cost of your DP is decided. This is also where you make problems tractable or hopeless: an under-specified state (missing a parameter the future depends on) gives wrong answers because distinct subproblems are conflated, while an over-specified state (an extra dimension you did not need) is correct but needlessly slow or memory-hungry. Much of advanced DP is the art of finding a state just rich enough to be correct and just lean enough to be fast.
For longest increasing subsequence, define dp[i] = length of the longest increasing subsequence ending exactly at index i. The clause 'ending at i' is what makes the state sufficient: it fixes the last element, so dp[i] can be built from dp[j] for earlier j with a[j] < a[i]. Define dp[i] as merely 'using the first i elements' and the state is too weak — the transition cannot tell whether a[i] can extend a given subsequence.
The right state fixes just enough (here, the last element) to make the future depend only on the state.
If your transition needs a fact about the past that the state does not record, the state is under-specified and will give wrong answers — fix the state, do not patch the transition with side data.