Dynamic Programming is bedeviled by the "curse of dimensionality", which is intensified by the expectations over the process noise. In this paper we present a Monte Carlo-based sampling of the state-space and an interpolation procedure of the resulting value function dependent on the process noise density in a "self-approximating" fashion. Proof of almost sure convergence is presented. The proposed sampling and interpolation algorithm alleviates the burden of gridding of Dynamic Programming and avoids the construction of a piecewise constant value function over the grid. The sampling nature, and the interpolation procedure of this approach make it adequate to deal with probabilistic constraints.