The existing techniques for shot partitioning either process each shot boundary independently or proceed sequentially. The sequential process assumes the last shot boundary is correctly detected and utilizes the shot length distribution to adapt the threshold for detecting the next boundary. These techniques are only locally optimal and suffer from the strong assumption about the correct detection of the last boundary. Addressing these fundamental issues, in this paper, we aim to find the global optimal shot partitioning by utilizing Bayesian principles to model the probability of a particular video partition being the shot partition. A computationally efficient algorithm based on Dynamic Programming is then formulated. The experimental results on a large movie set show that our algorithm performs consistently better than the best adaptive-thresholding technique commonly used for the task.