Dynamic programming can only be applied to problems with optimal substructure.
The Markov property (e.g. in Markov Decision Processes, MDPs) means that the distribution of one state $x_{k+1}$ only depends on the state directly before ($x_k$, and the action $a_k$), not on more steps before. (commonly expressed as $P(X_{k+1} = x_{k+1} | X_k = x_k, X_{k-1} = x_{k-1}, \dots, X_0 = x_0) = P(X_{k+1} = x_{k+1}| X_k = x_k )$)
What is the relationship between optimal substructure and the Markov property? Does every MDP have optimal substructure? What are examples of stochastic problems which have optimal substructure but do not have the Markov property? Or is there no such relationship?
