DP最关键的是整理出重叠子问题，从而得到动态转移方程或动态转移表。首先要定义清楚dp[i]=x的含义。以下是一些典型案例。
dp[i][w]=true/false 表示第i个物品选或者不选时，是否能达到w重量。
因此
选第i个物品时：dp[i][w+item[i]]=dp[i-1][w]
不选第i个物品时：dp[i][w] = dp[i-1][w]
两个字符串的最长连续子串
两个字符串的最长公共子序列
最长单调递增子串
最长单调递增子序列
原文：https://www.cnblogs.com/howo/p/12490608.html