算法很美笔记（Java）——动态规划

解重叠子问题（当前解用到了以前求过的解）

形式：记忆型递归或递推（dp）

动态规划本质是递推，核心是找到状态转移的方式，也就是填excel表时的逻辑（填的方式），而后代码就按填表的逻辑写即可

可以先写递归解法，发现有很多重叠子问题时，再改dp

递归是从大规模到小规模，记忆型递归或dp都是小规模到大规模

大多数情况，题中要求什么，dp的值就代表什么，比如求最大长度，dp值就是最大长度

01背包问题

使用dfs，分为选和不选

递归

static int[] wi = {1,5,10,50,100,500};static int[] vi = {1,5,1,0,10,2};public static int t1(int w,int curr) {if (w <= 0)  return 0;if (curr == wi.length) return 0;if (w < wi[curr]) {//            重量不够，选不上了return t1(w,curr++);} else {
//        不选int choice1 = t1(w,curr++);//         选int choice2 =  vi[curr] + t1(w - wi[curr],curr++);
//            返回的是选择树当前层以下的所有层的最优解
//            与本层的选择无关，所以不会出现因为不知道选还是不选比较大而导致的w混乱return Math.max(choice1,choice2);}}

dp

因为后面的行需要借助第一行的值填，所以先初始化第一行，再填后面的

物品编号也就是当前可选什么物品，编号以前的物品都能选，比如编号2，则第1~3个物品都能选。但是我们因为是借助前面填过的数据填，所以实际上，只需要考虑当前编号的物品的选与不选，而编号以前的物品通过“借助前面填过的数据填”时就已经选上了。

价值计算= 当前物品价值 +（上一行，可用重量）----->选

              =（上一行，可用重量）----->不选

eg：

表格（2，3），当前容量为3，物品重量为3，要的起，所以分为选与不选。

选：价值 = 4 +（1，0 ）= 4----->选

               =（1，3 ）= 5----->不选

因为每格需要借助其他格的值填，所以不能只考虑w的容量，而是要考虑0~w 之间的所有容量，而最终所求，是右下角的那个值。因为我们计算的是考虑所有物品的情况下（最后一行），容量为w（最后一列）的最大利润

static int[] wi = {1,5,10,50,100,500};static int[] vi = {1,5,1,0,10,2};public static int _01bag(int w) {
//        二维数组存储数据
//        重量0~wint[][] arr = new int[wi.length][w + 1];
//        初始化第一行数据for (int j = 0; j < w + 1; j++) {if (j >= wi[0]) {
//                要的起arr[0][j] = vi[0];} else {
//                要不起arr[0][j] = 0;}}
//利用前一行填当前行for (int i = 1; i < wi.length; i++) {for (int j = 0; j < w + 1; j++) {if (j >= wi[i]) {
//                要的起
//                    要int get = vi[i] + arr[i - 1][j - wi[i]];
//                    不要int noGet = arr[i - 1][j];arr[i][j] = Math.max(get,noGet);} else {
//                要不起arr[i][j] = arr[i - 1][j];}}}
//        取右下角作为结果return arr[wi.length - 1][w];}

完全背包

比01背包多了个条件：每种物品可以挑选任意多件。

dp

仍然初始化第一行，用以供给后面计算

虽然一个物品可以选多次，但是我们还是只分为选和不选

当不选时，思路和01背包相同（剩余重量在上一行中寻找最优解）

当选时，选一个后，剩余重量在同行中寻找最优解。

因为只要是填过的就是已经找到最优解的了，同一个物品，我们只需要选一次，至于最终要选几次，交给同行的最优解来解决

钢条切割

第一刀可以切1+9、2+8、3+7……

1+9的第二刀切9，可以切成1+8、2+7……

2+8的第二刀切8，可以切成1+7、2+6……

也就是，固定前面的一段，切后面一段。

因为如果两段都切会导致有很多重复结果比如2+8-->1+1 + 2+6和3+7-->1+2 + 1+6

因为是固定前面的一段，切后面一段，所以固定的的那一段长度可以直接得到价值，而只有后面那段价值不确定

递归

每切一刀就是一个递归，因为有不同切法，所以是for循环（控制切法）里写递归（控制刀数）

这样他们之间求max，就是结果（类似01背包问题的max，只不过01背包同层间都是两种选择，而本问题同层之间是不止两种）

static int[] v = {1 , 5 , 8 , 16 , 10 , 17 , 17 , 20 , 24 , 30};public static int cut(int x) {if (x == 0) return 0;
//        每刀切的长度1~10int maxSum = 0;for (int i = 1; i <= x; i++) {maxSum = Math.max(maxSum,(v[i-1] + cut(x - i)));}return maxSum;}

记忆型递归

这里会不止一次递归f（1）、f（2）……f（10），显然重复计算了

想改成只算一次，则用一个数组把这些值给记下来，当需要用的时候，如果有就直接用，没有就计算再存起来，以供后面计算使用

代码与直接递归类似

dp

画excel表为一个长度-价值最优表，不同长度的钢条对应不同价值

思路中，组合中第二段长度价值不确定，所以我们画了最优表，第二段价值直接取就行

最后求得长度为10的钢条的最大价值，return 价值

static int[] v = {1 , 5 , 8 , 16 , 10 , 17 , 17 , 20 , 24 , 30};public static int cut() {int[] sum = new int[11];sum[0] = 0;sum[1] = 1;for (int i = 3; i < 11; i++) {
//            curr初始为钢条不切，直接卖int curr = v[i - 1];for (int j = 1; j < i; j++) {int temp = v[j - 1] + sum[i - j];curr = Math.max(curr,temp);}sum[i] = curr;}return sum[10];}

数字三角形

The Triangle - POJ 1163 - Virtual Judge

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99输入格式：5 //表示三角形的行数 接下来输入三角形73 88 1 02 7 4 44 5 2 6 5
要求输出最大和

只能选左下，右下，而不是一层内可以随便选，所以无法一次性确定选什么最大，所以无法用贪心

那么就使用dfs把所有情况都列出来

可以看到，dfs会重复算中间的数，比如算第二层的3和8时，3算了f（1），8也算了f（1），所以用dp

从下往上填，最后一行没得选，直接初始化，其他行，找加起来更大的填上

static int[][] v = {{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5},};public static int Triangle() {int[][] arr = new int[5][5];
//        System.out.println(arr[3].length);
//        初始化一行for (int i = 0; i < 5; i++) {arr[4][i] = v[4][i];}
//        填其他行for (int i = arr.length - 2; i >= 0; i--) {
//            列for (int j = 0; j < i + 1; j++) {arr[i][j] = Math.max(v[i][j] + arr[i+1][j],v[i][j] + arr[i+1][j+1]);}}return arr[0][0];}

最长公共子序列（LCS）

子数组只能像截取一段这样，是紧凑的

而子序列可以跳着来，只要前后顺序一致就行

比如AB34C和A1BC2 则输出ABC

找出全部公共子序列，然后求max

有串S1 = AB34C ，S2 = A1BC2

让S1的每一个字母都作为一个子序列的开头

eg：让A作为开头，则去S2里找A，找到了的话，通过将后面未处理的序列进行递归和字符串拼接将后续子序列拼接出来。没找到则不用处理，这样max的时候就不会被取

这样处理完A开头的子序列后，处理B开头的子序列……

将这些子序列取长度max返回

用ArrayList存结果

for i ：S1每个开头

        for j：S2 找相同字母

                找到了：当前字母+递归（剩余子串）

        if（上一个子序列.size()<当前子序列.size()）res = 当前子序列

public static ArrayList<Character> str(String s1,String s2) {
//        让s1的，每一个字母开头ArrayList<Character> endRes = new ArrayList<>();for (int i = 0; i < s1.length(); i++) {ArrayList<Character> res = new ArrayList<>();
//            去s2找匹配的for (int j = 0; j < s2.length(); j++) {if (s1.charAt(i) == s2.charAt(j)) {res.add(s1.charAt(i));res.addAll(str(s1.substring(i + 1),s2.substring(j + 1)));break;}}if (res.size() > endRes.size()) {endRes = res;}}return endRes;}

最长上升子序列问题

有一个长为n的数列a0,a1,...,a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列。1≤n≤10000≤ai≤1000000输入n=5
a={4,2,3,1,5}
输出3（注：2，3，5）

因为是子序列，所以可以跳着取

暴力法

类似上一题的思路

以每一个数字开头，遍历向后找比这个数字大的数字，剩余数字用递归找

而后所有子序列求max 

dp

dp的每个值代表：以这个数字作为结尾，由它前面的数字组成的最长子序列的长度

curr是当前数字，

与前面每个数字做比较，自己较大，则curr的一个dp值等于 前面的数字的dp值+1，自己较小则urr的一个dp值等于 1（子序列只有自己，长度就是1）

再与更前面的数字作比较，求出一个dp值

…………

等与前面的每个数字作比较求出dp值后，取最大的dp值为最终dp值

求完所有dp值后，取最大的值作为结果返回

public static int maxLen(int[] a) {if (a.length == 0) return 0;int[] dp = new int[a.length];dp[0] = 1;for (int i = 1; i < dp.length; i++) {
//            子序列只有自己的时候的lengthint res = 1;
//            与前面的元素作比较for (int j = i - 1; j >= 0 ; j--) {
//                较小，子序列length就是1
//                较大if (a[j] < a[i]) {int temp = dp[j] + 1;
//                    取maxif (res < temp) {res = temp;}}}dp[i] = res;}return max(dp);}public static int max(int[] dp) {int maxVal = 0;for (int i = 0; i < dp.length; i++) {if (dp[i] > maxVal) {maxVal = dp[i];}}return maxVal;}public static void main(String[] args) {System.out.println(maxLen(new int[]{4,2,3,1,5}));}