Nussinov 1978 RNA folding: M(i,j) = max{M(i+1,j), M(i,j−1), M(i+1,j−1)+δ_{ij}, max_k M(i,k)+M(k+1,j)}

Nussinov 1978 RNA-secondary-structure folding — the canonical dynamic-programming (DP) framework for maximum-base-pair RNA folding. Physical setup: given an RNA sequence s[0..n−1], find the secondary structure (set of non-crossing base…