DP即“动态规划”，是一种常见的算法思想，通常用来求解最优化问题。DP M则是指“DP Memoization”，是一种优化DP算法的方式。
在DP算法中，通常需要用到递推公式来计算最优解。递推的过程中会重复计算一些子问题，而DP M的作用就是将这些子问题的结果保存下来，避免重复计算，从而加速运算。
DP M的实现方法很简单，通常可以使用一个数组来保存已经计算过的子问题结果。每次计算一个子问题的结果时，先检查数组中是否已经保存过这个问题的结果，如果有，则直接返回保存的结果，否则进行计算，同时将计算结果保存到数组中。
需要注意的是，这个数组的大小需要根据实际情况来决定，一般来说，数组的大小要根据最大的子问题规模来设定。如果子问题规模很大，那么数组可能会占用很大的内存，这时可以考虑使用哈希表等数据结构来优化。
DP M的优点是能够避免重复计算，从而减少运算时间。在一些问题中，DP M甚至可以将计算时间从指数级别降到多项式级别。
缺点是DP M需要使用额外的空间来保存已经计算过的子问题结果，因此会占用更多的内存。此外，DP M的实现比较简单，但是也需要一定的编程技巧来实现。
DP M通常用于求解重复子问题的最优化问题，例如编辑距离、最长子序列、最长公共子序列等。在这些问题中，DP M可以显著提高算法的效率。
另外，DP M还可以用于优化一些递归算法，例如斐波那契数列问题。传统的斐波那契解法是使用递归算法，但是这种算法时间复杂度很高，因为同一个子问题会反复被递归计算。使用DP M可以避免这种情况，从而大大提高算法效率。
关注微信