一、适用场景

重复子问题，或问题的解由最优子结构组成。
比如：最大和的子序列问题，其解是由去掉最后一个数之后，整个序列的相同问题，“最大和的子序列”，这一重复子问题的最优子结构解组成的。

二、步骤

1. 确定状态

   具体来说，就是dp[i]的具体含义。
   几种常见题目的状态：

   1. 跳跃游戏：数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

   维护一个能达到的最大距离。一次循环不停更新，最终最大距离大于长度则能到达最后。

   1. 零钱兑换：给定数组表示零钱的所有面额，判断需要多少个零钱才能凑到总额。

   dp[i]表示总额为i时需要的零钱数。

   1. 最长递增子序列：找到数据中最长递增子序列（可不连续）的长度。

   dp[i]表示以下标i位置结尾的最长递增子序列的长度。

   1. 最长公共子序列：两个字符串中最长公共子序列的长度。 dp[i][j]表示第一个串的0-i位置的子串与第二个串的0-j位置的子串的最长公共子序列长度。 213. 打家劫舍 II：数组表示围成一圈的房子，不能偷相邻房子，偷的总额最大多少。 围成一圈的问题分成两种情况，第一种第一个房子不偷，可偷的范围为1-n； 第二种最后一个房子不偷，可偷的范围为0-n-1。 两种情况通用，dp[i]表示从第一个可偷的房子到下标i位置处，能偷到的最大金额。

1. 状态转移的步骤

dp[i]如何与前面的dp[j] (j<i)发生联系。在具体实现时，需要注意状态转移的顺序。

1. 初始条件
2. 终止条件
3. （优化）。若dp[i]只和前面有限的状态相关，可以用滑动窗口的方法，降低空间复杂度从O(n)到O(1)。

比如dp[i]=dp[i-1]+dp[i-2]，fore, back, temp;
temp=fore; fore=back; back=新的back表达式。