1.如果是0-1背包，即数组中的元素不可重复使用；
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]=max(f[j], f[j-a[i]]+b[i]);
}
}
2.如果是完全背包，即数组中的元素可重复使用。
for(int i=1;i<=n;i++){
for(int j = a[i];j <= m;j++){
f[j] = max(f[j], f[j-a[i]]+b[i]);
}
}
3.多重背包
for (int i = 0; i < P.length; i++){
for (int j = 0; j <= T; j++){
for (int k = 0; k <= M[i] && k * V[i] <= j; k++){
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j-k * V[i]] + k * P[i]);
}
}
}
问题描述：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums:
for i in range(target, num-1, -1):
dp[i] += dp[i - num]
2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums:
for i in range(num, target+1):
dp[i] += dp[i - num]
3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1):
for num in nums:
if (i >= num):
dp[i] += dp[i - num]
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length < 1) return 0;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++){
for (int num : nums){
if (i >= num){
dp[i] += dp[i - num];
}
}
}
return dp[target];
}问题描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)dp[i][0] = i;
for (int i = 1; i <= n; i++)dp[0][i] = i;
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
if (word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = 1 + min(dp[i - 1][ j - 1], dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
public int min(int a, int b, int c){
int tmp = a < b ? a : b;
return Math.min(tmp, c);
}问题描述：给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
解析：dp[i][j][len]描述s1以i为起点，s2以j为起点长度为len的两个字符串是不是扰乱字符串
转移公式见代码
public boolean isScramble(String s1, String s2) {
int n = s1.length();
int m = s2.length();
if (n != m)return false;//若是不等长则一定不是扰乱字符串
boolean[][][] dp = new boolean[n][m][n + 1];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
//当长度为1的时候，若是俩字符相等则dp[i][j][1]
dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
}
}
for (int len = 2; len <= n; len++){//从长度为2开始遍历
for (int i = 0; i <= n - len; i++){
for (int j = 0; j <= n - len; j++){
for (int k = 1; k < len; k++){
//第一种情况：存在一个k使得讲过k划分后s1的前半段与s2的前半段匹配，且s1的后半段与s2的后半段匹配
if (dp[i][j][k] && dp[i + k][j + k][len - k]){
dp[i][j][len] = true;
break;
}
//第二种情况：//存在一个k使得讲过k划分后s1的前半段与s2的后半段匹配，且s1的后半段与s2的前半段匹配
if (dp[i][j + len - k][k] && dp[i + k][j][len - k]){
dp[i][j][len] = true;
break;
}
}
}
}
}
return dp[0][0][n];
}问题描述：一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
public int numDecodings(String s) {
int[] dp = new int[s.length() + 1];
char[] ms = s.toCharArray();
dp[0] = 1;
dp[1] = 1;
if (s.charAt(0) == '0')return 0;
for (int i = 1; i < s.length(); i++){
if ((ms[i - 1] == '1' && ms[i] != '0' ) || (ms[i - 1] == '2' && ms[i] > '0' && ms[i] <= '6')){
dp[i + 1] = dp[i] + dp[i - 1];
}else if ((ms[i - 1] == '1' || ms[i - 1] == '2') && ms[i] == '0'){
dp[i + 1] = dp[i - 1];
}else{
if (s.charAt(i) == '0')return 0;
dp[i + 1] = dp[i];
}
}
return dp[s.length()];
}问题描述：给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
解析：
设定：G(n): 长度为n的序列能构成的不同二叉搜索树的个数。
F(i, n): 以i为根、序列长度为n的不同二叉搜索树个数。
明显有：G(n)=∑F(i,n)
另有：F(i,n)=G(i−1)⋅G(n−i)
可以推导出：G(n)=∑G(i−1)⋅G(n−i)
//先序
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int len = 2; len <= n; len++){
for (int i = 1; i <= len; i++){
dp[len] += dp[i - 1] * dp[len - i];
}
}
return dp[n];
}问题描述：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的
解析：dp[i][j]s1的前i个字符与s2的前j个字符能不能构s3的前i+j个字符
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length(), p = s3.length();
if (n + m != p)return false;
if (n == 0)return s2.equals(s3);
if (m == 0)return s1.equals(s3);
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
//下面两层循环为初始状态的设定：若是s1的前i个字符能描述s3的前i个字符，则dp应设为true
for (int i = 0; i < n; i++){
if (s1.charAt(i) != s3.charAt(i))break;
dp[i + 1][0] = true;
}
for (int i = 0; i < m; i++){
if (s2.charAt(i) != s3.charAt(i))break;
dp[0][i + 1] = true;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
dp[i][j] = (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
}
}
return dp[n][m];
}