ABSTRACT. Dynamic Programming solves optimization problems over an exponential search space in polynomial time. Bellman's Principle of Optimality is its mathematical prerequisite. Recursion and tabulation of intermediates are its essential ingredients to achieve efficiency. While these basic principles are well- understood, still such algorithms are intricate to develop and hopeless to debug. An optimal solution to a dynamic programming (DP) problem is identified by its optimal score. Recording the function calls which compute a score value gives us an uninterpreted term that can be understood as data structure representing the solution – and the algebra of all such terms (optimal or not) represents the search space for the given problem input. With ICOREs, we describe the search universe of a DP problem by a language of abstract terms. A set of rewrite rules relates the solutions to the problem input for which they constitute the search space. An evaluation algebra collapses solutions into their associated scores. A choice function operates on scores to identify optimal solutions. The issues of search, scoring and optimization are prefectly separated. These four constituents specify a DP problem in a perfectly declarative way. All we need now is a compiler to construct code that computes the inverse of the rewrite relation (starting from the input), evaluates and tabulates partial solutions, and applies Bellman's optimization rule along the way.