目录

1.背包问题

1.1 题目描述

1.2 画图分析

1.3 思路分析

1.4 代码示例

2. 回文串分割

2.1 题目描述

2.2 思路分析

2.3 代码示例

---

1.背包问题

1.1 题目描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小
和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?1.A[i], V[i], n, m 均为整数
2.你不能将物品进行切分
3.你所挑选的要装入背包的物品的总大小不能超过 m
4.每个物品只能取一次
5.m <= 1000
len(A),len(V)<=100

1.2 画图分析

• 第 i 个商品放入包中的价值

此时两个等式其实都可以由 F(i, j) = F(i - 1, j - a[i -1]) + v[i -1]  来代替 

•  第 i 个商品的大小 > 包的大小

此时 F(i, j) = F(i - 1, j) 

1.3 思路分析

状态 F(i, j)：从前 i 个商品中选择，包的大小为 j 时的最大价值。（商品的索引从 1 开始，数组的索引从 0 开始）

状态转移方程：

• a[i - 1]  >  j             F(i, j) = F(i - 1, j)
• a[i - 1] <= j             F(i, j) = F(i - 1, j - a[i - 1]) + v[i - 1]

初始状态：F(i, 0) = F(0, j) = 0，由于每一个商品的价值都可能和前一行的某一列有关，为了防止数组越界，我们申请一个行，列比商品数、包都大一的二维数组 array[n + 1][m + 1].

返回结果：array[n][m].

结合具体示例理解：

 

1.4 代码示例

public class Solution {public static int backPackII(int m, int[] a, int[] v) {int number = a.length;int[][] array = new int[number + 1][m + 1];// 初始状态 array[0][j] = array[i][0] = 0for(int i = 1; i < number + 1; i++) {for(int j = 1; j < m + 1; j++) {// 状态转移方程if(a[i - 1] > j) {array[i][j] = array[i - 1][j];} else {array[i][j] = Math.max(array[i -1][j], array[i - 1][j - a[i - 1]] + v[i - 1]);}}}// 返回结果return array[number][m];}
}

【优化】一维数组

上述代码可以优化为只用一个一维数组，循环还是两层，但是要注意的是：内层循环需要从后往前走，因为状态方程需要用未更新之前的值，如果从小到大更新的话，我们是先更新前面这些列的值，那么后面使用的就都是更新过的值了；但是对于二维数组，从前往后，从后往前都是可以的。

public class Solution {public int backPackII(int m, int[] a, int[] v) {int number = a.length;// 省去行int[] array = new int[m + 1];for(int i = 1; i < number + 1; i++) {// 注意从后往前更新for(int j = m; j > 0; j--) {if(a[i - 1] <= j) {// 状态转移方程array[j] = Math.max(array[j], array[j - a[i - 1]] + v[i - 1]);}}}return array[m];}
}

2. 回文串分割

2.1 题目描述

给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1，因为回文分割结果["aa","b"]是切割一次生成的。

示例1：

输入："aab"
返回值：1

2.2 思路分析

问题：s 的最小分割次数

状态 F(i) ：s 的前 i 个字符最小的分割次数

状态转移方程：

• [1, i] 是回文串      array[i] = 0;
• [1, i] 不是回文串，且 i < j && [j + 1, i] 是回文串        min(F(i), F(j) + 1);

初始状态：F(i) = i - 1 ，i  从 1 开始

返回结果：F(s.length())

结合具体实例理解 min(F(i), F(j) + 1)  :

 

2.3 代码示例

public class Solution {public boolean isPal(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}public int minCut (String s) {if(s.length() == 0 || s.length() == 1) {return 0;}int[] array = new int[s.length() + 1];// 初始状态for(int i = 1; i < array.length; i++) {array[i] = i - 1;}for(int i = 2; i < array.length; i++) {// 判断整体是否为回文串if(isPal(s.substring(0,i))) {array[i] = 0;} else {for(int j = 1; j < i; j++) {// j < i && [j + 1, i] 是否为回文串if(isPal(s.substring(j, i))) {// 状态转移方程array[i] = Math.min(array[i], array[j] + 1);}}}}return array[s.length()];}
}