dp接什么 DP怎么选？-5到20左右

1、dp接什么

dp是动态规划的简称，是一种高效解决问题的算法，可以用于求解最优化问题。在使用dp算法时，我们要考虑接什么？接哪些参数？这些问题的答案都影响着dp算法的表现。下面我们就来详细讨论dp接什么问题。

2、找到最优子结构

为了使用dp算法，我们需要找到最优子结构，即问题可以分成独立的子问题进行解决，并且子问题的最优解可以推导出原问题的最优解。在找到最优子结构之后，我们就可以开始考虑dp接什么问题了。

3、dp接状态

dp算法是通过状态转移方程来得到最优解的，因此在使用dp算法时，我们要考虑dp接哪些状态。具体而言，状态一般与问题的解有关，因此要根据问题的不同来确定dp接哪些状态。

举个例子，假设我们要求解最长上升子序列的长度，那么状态可以用一个一维数组dp表示，其中dp[i]表示以第i个元素结尾的最长上升子序列的长度。这时候我们需要dp接的状态就是dp[i-1]，也就是说，当前元素的最长上升子序列长度与前一元素的最长上升子序列长度有关。

4、dp接转移方程

最后，我们需要考虑dp接什么转移方程。当我们确定好状态以后，我们就可以从状态转移方程入手来解决问题。具体而言，状态转移方程描述了子问题之间的转移关系。

还是以求解最长上升子序列的长度为例，状态转移方程可以表示为：

当 nums[i] > nums[j] 时，dp[i] = max(dp[i], dp[j] + 1)，其中 i > j，0 <= j < i。

这个转移方程表示了以当前元素结尾的最长上升子序列的长度可以由前面的最长上升子序列长度转移而来，转移方程中关键的地方是max(dp[i], dp[j] + 1)，即通过取max得到当前元素结尾的最长上升子序列长度。