The key observation for dynamic programming is to merge "equivalent states" in the same beam (i.e., same step) if they have the same feature values, because they will have the same costs as shown in the deductive system in Figure 1.
we can define two states j, S and j ′ , S ′ to be equivalent, notated j, S ∼ j ′ , S ′ , iff.