Dynamic Programming (DP) based Track-Before-Detect (TBD) algorithm is effective in detecting low signal-to-noise ratio (SNR) targets. However, its complexity increases exponentially as the dimension of the target state space increases, so the exact implementation of DP-TBD will become computationally prohibitive if the state dimension is more than two or three, which greatly prevents its applications to many realistic problems. In order to improve the computational efficiency of DP-TBD, a thresholding process based DP-TBD (TP-DP-TBD) is proposed in this paper. In TP-DP-TBD, a low threshold is first used to eliminate the noise-like (with low-amplitude) measurements. Then the DP integration process is modified to only focuses on the thresholded higher-amplitude measurements, thus huge amounts of computation devoted to the less meaningful low-amplitude measurements are saved. Additionally, a merit function transfer process is integrated into DP recursion to guarantee the inheritance and utilization of the target merits. The performance of TP-DP-TBD is investigated under both optical style Cartesian model and surveillance radar model. The results show that substantial computation reduction is achieved with limited performance loss, consequently TP-DP-TBD provides a cost-efficient tradeoff between computational cost and performance. The effect of the merit function transfer on performance is also studied.