贪心策略和动态规划学习。

一、贪心策略

1、贪心策略简介

• 动态规划和贪心算法都是一种递推算法均用局部最优解来推导全局最优解。
• 是对遍历解空间的一种优化。
• 当问题具有最优子结构时，可用动规，而贪心是动规的特例。

什么是贪心策略：

• 遵循某种规则,不断(贪心地)选取当前最优策略,最终找到最优解。
• 难点:当前最优未必是整体最优。

2、硬币问题

• 尽量先用大面值，因为不用大面值，将使用更多的小面值，一定得不到最优解。

package 贪心算法;//硬币问题import java.util.Scanner;/*** 有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.* 现在要用这些硬币来支付A元,最少需要多少枚硬币?** 限制条件:* 0≤ C1,C5,C10,C50,C100,C500≤1000000000* 0≤A≤1000000000** 输入描述:* 依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔.** 输出描述:* 输出最少所需硬币数.** 示例1:* 输入* 3 2 1 3 0 2 620* 输出* 6*/
public class Demo01 {static int[] counts = new int[6];//存放硬币的枚数。static int[] coins = {1,5,10,50,100,500};//硬币的价值。public static void main(String[] args) {Scanner scanner = new Scanner(System.in);for (int i = 0; i <6; i++) {counts[i] = scanner.nextInt();}int A = scanner.nextInt();int res = f(A,5);System.out.println(res);}//尽量先用大面值，因为不用大面值，将使用更多的小面值，一定得不到最优解。public static int f(int A,int cur){   //cur为下标，让下标递减，表示用的面值从大到小。if(A<=0) return 0;if (cur==0) {//到了最小面值硬币了。if (counts[cur]>=A) {//剩下钱比1元数量多。return A;}else{System.out.println("NOWAY");System.exit(0);//正常退出程序。}}int coinValue = coins[cur];int x = A/coinValue;   //用此硬币的枚数。int count = counts[cur];//此硬币有多少枚。int t = Math.min(x,count);//取最多能拿出的枚数。return t + f(A-t*coinValue,cur-1);//用t个当前面值，剩下的递归。}
}

2、快速渡河

• 第一种方案：用最快的1去带最慢的，让最快1回来，再让用最快的1去带第二慢的，让最快1回来，直到全部带过去。
• 第二种方案：先让最快的1,2过去，1回来，再让左边选最慢的两个过去，2回来，这样可以先运输最慢的两个，而且使慢的不参与返回，始终让最快的1,2参与返回。此案例显然这种情况更好，但是也不是绝对的。

package 贪心算法;//快速渡河import java.util.Arrays;
import java.util.Scanner;/*** N个人希望只乘一条船过河，每条船最多只能载两个人。因此，必须安排谁去与回来，以便所有人最快过河。* 每个人都有不同的划船速度；两个人速度取决于较慢者。请给出时间最短的策略。** 输入值:* 输入的第一行包含一个整数T（1 <= T <= 20），即测试案例的数量。* 然后是T个案例。每个案例的第一行包含N，第二行包含N个整数，给出每个人过河的时间。每个案例前面都有一个空行。* 不会有超过1000人，而且没有人需要超过100秒来过河。** 输出量:* 对于每个测试用例，打印一行N个人穿过河流所需的总秒数。** 样本输入:* 1* 4* 1 2 5 10* 样本输出:* 17*/
public class Demo02 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();//输入T个案例for (int i = 0; i < T; i++) {int n = scanner.nextInt();int[] speed = new int[n];for (int j = 0; j < n; j++) {speed[j] = scanner.nextInt();}Arrays.sort(speed);//将speed从小到大进行排序。f(n,speed);}}private static void f(int n,int[] speed){int left = n;//还没过岸的人数int ans = 0;//总秒数while (left>0){if (left==1){//有1个人ans += speed[0];break;}else if (left==2){//有2个人ans += speed[1];break;}else if (left==3){//有3个人ans += speed[2]+speed[0]+speed[1];break;}else {//两种过河的方式：// 1，2出发，1返回，最后两名出发，2返回。int s1 = speed[1]+speed[0]+speed[left-1]+speed[1];//1，3出发，1和最后一名出发，1返回，1再和到第二名出发，1返回。int s2 = speed[0]*2+speed[left-1]+speed[left-2];ans += Math.min(s1,s2);//取这两种方案最好的。left = left-2;//左侧代表是渡河的起点，left代表左侧的剩余人数。一次过两个.}}System.out.println(ans);}
}

3、区间调度问题

• 将所有的工作结束的时间从小到大排列，以第一个工作的结束时间为初始值，保证了从起始点到该点之间，该事件的时间最短。然后判断下一个事件开始时间是否大于结束时间，若大于则执行该事件，更新初始值，继续判断下一事件，否则跳过该事件，判断下一个事件。

package 贪心算法;//区间调度问题import java.util.Arrays;
import java.util.Scanner;/*** 有n项工作,每项工作分别在s时间开始,在t时间结束.对于每项工作,你都可以选择参与与否.* 如果选择了参与,那么自始至终都必须全程参与.此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).* 你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?** 1≤n≤100000* 1≤s≤t≤109** 输入:* 第一行:n* 第二行:n个整数空格隔开,代表n个工作的开始时间* 第三行:n个整数空格隔开,代表n个工作的结束时间** 样例输入:* 5* 1 3 1 6 8* 3 5 2 9 10** 样例输出:* 3* 说明:选取工作1,3,5.*/
public class Demo03 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] s = new int[n];//工作的开始时间。int[] t = new int[n];//工作的结束时间。Job[] jobs = new Job[n];//建一个数组存放工作对象。for (int i = 0; i < n; i++) {s[i] = scanner.nextInt();}for (int i = 0; i < n; i++) {t[i] = scanner.nextInt();}for (int i = 0; i < n; i++) {jobs[i] = new Job(s[i],t[i]);}//根据重写的compareTo()方法的返回结果，进行排序。Arrays.sort(jobs);int res = f(n,jobs);System.out.println(res);}private static int f(int n,Job[] jobs){int cnt = 1;//工作的次数。int y = jobs[0].t;//第一个工作结束的时间。for (int i = 0; i < n; i++) {if (jobs[i].s>y){cnt++;y = jobs[i].t;}}return cnt;}private static class Job implements Comparable<Job>{int s;int t;public Job(int s, int t) {this.s = s;this.t = t;}@Overridepublic int compareTo(Job o) {//先按结束时间比，结束时间相同的话，再按开始时间比。从小到大排序。int x = this.t-o.t;if (x==0){return this.s-o.s;}else {return x;}}}
}

4、区间选点问题

• 新建一个标记数组来记录点。先将每个区间按照结束时间的从小到大排列，然后查阅标记数组中这个区间中有多少个点，用需要的点数减去已经标记的点数就是还需要标记的点数；如果不够，从区间右端开始标记，遇标记过的就跳过，最后统计标记数组上一共的点数。

package 贪心算法;//区间选点问题
import java.util.Arrays;
import java.util.Scanner;/*** 给定n个整数闭区间，以及他们需要命中点的数目，设计程序求出最少需要多少个点.** 输入值:* 输入的第一行包含一个整数n (1 <= n <= 50000) -- 间隔的数量。* 接下来的n行描述了这些区间。输入的第(i+1)行包含三个整数ai, bi和ci，它们之间用单空格隔开，* 并使0 <= ai <= bi <= 50000和1 <= ci <= bi - ai+1。** 输出量:* 最少需要的点数.** 样本输入:* 5* 3 7 3* 8 10 3* 6 8 1* 1 3 1* 10 11 1* 样本输出:* 6*/
public class Demo04 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();Interval[] intervals = new Interval[n];for (int i = 0; i < n; i++) {//输入n组对象。intervals[i] = new Interval(scanner.nextInt(),scanner.nextInt(),scanner.nextInt());}Arrays.sort(intervals);//按区间右建点排序。int max = intervals[n-1].t;//右端的最大值int[] axis = new int[max+1];//新建一个数组，用来标记数轴上的点是否已经被选中。for (int i = 0; i < n; i++) {//1.查阅区间中有多少个点int s = intervals[i].s;//起点int t = intervals[i].t;//终点int cnt = sum(axis,s,t);//找到这个区间已选点的数量。//2.如果不够，从区间右端开始标记，遇标记过的就跳过。intervals[i].c -= cnt;//需要新增点的数量。while (intervals[i].c>0){if (axis[t]==0){   //从区间终点开始选点axis[t]=1;intervals[i].c--;  //进一步减少需要新增点的数量。t--;}else {//这个点已经被选过了。t--;}}}System.out.println(sum(axis,0,max));}//统计数轴axis上s-t已经有多少个点。private static int sum(int[] axis,int s,int t){int sum=0;for (int i = s; i <=t; i++) {sum +=axis[i];}return sum;}//把起始点和结束点以及需要标记的点数，打包成一个对象。private static class Interval implements Comparable<Interval>{int s;int t;int c;public Interval(int s, int t, int c) {this.s = s;this.t = t;this.c = c;}@Overridepublic int compareTo(Interval o) {//先按结束点大小排序，结束点一样的话，再按起始点大小排序。int x = this.t-o.t;int y = this.s-o.s;return x!=0?x:y;}}
}

5、区间覆盖问题

• 先把区间按照开始时间从小到大排序。如果第一个区间不能覆盖start，则直接无解；若区间能覆盖start，取当时end和最靠右的端点（t）的最大值作为新的end；当不能覆盖时，更新start=end+1，计数+1,再判断如果头过了新的start，更新end，否则无解。在循环中如果end到了最后的T，直接结束循环。

package 贪心算法;//区间覆盖问题import java.util.Arrays;
import java.util.Scanner;/*** 农夫约翰正在分配他的N头（1 <= N <= 25,000）牛在谷仓周围做一些清洁工作。* 他一直想让一头母牛进行清理工作，并将一天分为T个时间段（1 <= T <= 1,000,000），第一个是间隔1，最后一个间隔是T。* 每头牛只能在特定的时间段进行清洁工作。任何被选定的牛将在整个时间段内工作。* 您的工作是帮助农夫约翰分配一些奶牛到时间段，以便（i）每个班次至少分配一头奶牛，并且（ii）尽可能少地母牛参与清洁工作。* 如果无法实现所有时间段内都有牛工作，则打印-1。** 输入值：* 第1行：两个以空格分隔的整数：N和T* 第2…N + 1行：每行包含母牛可以工作的时间段开始和结束时间。母牛在开始时间开始工作，在结束时间之后结束。** 输出量：* 第1行：农夫约翰需要雇用的最小母牛数或如果无法实现所有时间段内都有牛工作，-1。** 样本输入：* 3 10* 1 7* 3 6* 6 10* 样本输出：* 2*/
public class Demo05 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int T = scanner.nextInt();Job[] jobs = new Job[N];for (int i = 0; i < N; i++) {jobs[i] = new Job(scanner.nextInt(),scanner.nextInt());}Arrays.sort(jobs);int start = 1;//要覆盖的目标点，end覆盖该点的所有区间的右端点最右。int end = 1;int ans = 1;//雇佣的母牛数。for (int i = 0; i < N; i++) {int s = jobs[i].s;int t = jobs[i].t;if (i==0 && s>1) break;//最小开始时间都大于1.if (s<=start){   //当前区间有可能覆盖start.此时不需要更新start，更新end。end = Math.max(t,end);  //更新最右的端点.} else {   //此时start和end都要更新。开始下一个区间.ans++;   //上一个目标覆盖已经达成，计数加1！start = end+1;   //更新起点，设置一个新的覆盖目标。//由于是区间，不是每个点的端点。例如比如[1,3] [4,7] ,中间时间段是连续的。if (s<=start){end=Math.max(t,end);}else {break;}}if (end>=T){  //当前的end超越了线段的右侧。break;}}if (end<T){System.out.println(-1);}else {System.out.println(ans);}}private static class Job implements Comparable<Job>{int s;int t;public Job(int s, int t) {this.s = s;this.t = t;}@Overridepublic int compareTo(Job o) {//按照区间的起点排序int x = this.s-o.s;if (x==0){return this.t-o.t;}else {return x;}}}
}

6、字符最小问题

• 先将字符串反转，用compare()方法比较两个字符串的头(当开头相同时，会比较第二个字符)，取最小的作为新字符串的头。

package 贪心算法;//字符最小问题import java.util.Scanner;/*** 给一个定长为N的字符串S,构造一个字符串T,长度也为N。* 起初，T是一个空串，随后反复进行下列任意操作:1或2。* 1。从S的头部删除一个字符，加到T的尾部.* 2。从S的尾部删除一个字符，加到T的尾部.* 目标是最后生成的字符串T的字典序尽可能小.* 1≤N≤2000.* 字符串S只包含大写英文字母.** 输入：字符串S* 输出：字符串T** 样本输入:* 6* A* C* D* B* C* B* 样本输出:* ABCBCD*/
public class Demo06 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();//StringBuilder : 可边长字符串.StringBuilder ss = new StringBuilder();for (int i = 0; i < N; i++) {ss.append(scanner.next());}f(ss.toString());}private static void f(String s){String s1 = new StringBuilder(s).reverse().toString();//反转字符串int N = s.length();StringBuilder rs = new StringBuilder();int cnt = 0;while (rs.length()<N){/*compareTo();1，长度相同,从第一位开始比较，如果相同返回0，如果不同则马上返回这两个字符的ascii值的差值。2，长度不同,直接返回长度差值。*/if (s.compareTo(s1)<0){rs.append(s.charAt(0));s =s.substring(1);//去掉第一个元素。}else {rs.append(s1.charAt(0));s1 =s1.substring(1);}if (rs.length()%80==0){   //80位换行。System.out.println(rs.substring(cnt*80,(cnt+1)*80));cnt++;}}if (rs.length()>cnt*80){System.out.println(rs.substring(cnt*80));}}
}

7、最优装载问题

• 先装轻的物体，再装重的物体。

package 贪心算法;import java.util.Arrays;
import java.util.Scanner;//最优装载问题
//给出n个物体，第i个物体重量为wi。选择尽量多的物体，使得总重量不超过C。
public class Demo07 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] w = new int[n];for (int i = 0; i < n; i++) {w[i] = scanner.nextInt();}int C = scanner.nextInt();Arrays.sort(w);int ans = f(n,w,C);System.out.println(ans);//最多能装多少物体。}private static int f(int n,int[] w,int c){int sum = 0;   //装的物体的重量。int cnt = 0;   //装的物体的个数。for (int i = 0; i < n; i++) {sum += w[i];if (sum<=c){cnt++;}else {break;}}return cnt;}
}

8、背包部分问题

• 先把所有物品按照性价比从小到大（价值/重量）排序。先把拿性价比高的全都拿走，当背包装不了的时候，再按重量取走部分物品。

package 贪心算法;//背包部分问题import java.util.Arrays;/*** 有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。* 每一个物体都可以只取走一部分，价值和重量按比例计算。求最大总价值.* 注意：每个物体可以只拿一部分，因此一定可以让总重量恰好为C。*/
public class Demo08 {public static void main(String[] args) {int[] w = {1,2,3,4,5};int[] v = {3,4,3,1,4};int n = w.length;double C = 10;Obj[] objs = new Obj[n];for (int i = 0; i < n; i++) {objs[i] = new Obj(w[i],v[i]);}Arrays.sort(objs);double c = C;double maxValue = 0;   //能拿走的最大价值。//从最大性价比开始拿。for (int i = n-1; i >=0; i--) {if (objs[i].w<=c){maxValue += objs[i].v;c -=objs[i].w;}else {//拿一部分。//maxValue += objs[i].v * (c / objs[i].w);//maxValue += c * (objs[i].v / (double)objs[i].w);maxValue += c*objs[i].getPrice();break;}}System.out.println(maxValue);}private static class Obj implements Comparable<Obj>{int w;int v;public Obj(int w, int v) {this.w = w;this.v = v;}//性价比public double getPrice(){return v/(double)w;}@Overridepublic int compareTo(Obj o) {//按照性价比从小到大排序。if (this.getPrice()== o.getPrice()) return 0;else if (this.getPrice()< o.getPrice()) return -1;else return 1;}@Overridepublic String toString() {return "Obj{" +"w=" + w +", v=" + v +",price"+getPrice()+'}';}}
}

9、乘船问题

• 先考虑最轻的人，如果每个人都无法和他一起坐船(重量和超过C)，则唯一的方案是每个人坐一艘。否则，他应该选择能和他一起坐船的人中最重的一个。

package 贪心算法;//乘船问题import java.util.Arrays;/*** 有n个人，第1个人重量为wi。每艘船的最大载重量均为C，且最多只能乘两个人。用最少的船装载所有人。** 贪心策略:考虑最轻的人i，如果每个人都无法和他一起坐船(重量和超过C)，则唯一的方案是每个人坐一艘。* 否则，他应该选择能和他一起坐船的人中最重的一个。** 求需要船的数量。*/
public class Demo09 {public static void main(String[] args) {int[] w = {1,2,3,4,5,6,7,8,9,10};int n = w.length;int c = 10;Arrays.sort(w);int countOfPerson = n;   //还未到岸的人数。int countOfBoot = 0;   //需要船的数量。int p1 = 0;   //指向第一个人。int p2 = n-1;   //指向最后一个人。while (countOfPerson>0){if (w[p1]+w[p2]>c){   //超重了，让重的自己过岸。p2--;countOfPerson--;countOfBoot++;}else {   //两个人过岸p1++;p2--;countOfPerson -= 2;countOfBoot++;}}System.out.println(countOfBoot);}
}

10、总结

• 最优子结构:对比dfs ,不是进行各种可选支路的试探,而是当下就可用某种策略确定选择,无需考虑未来(未来情况的演变也影响不了当下的选择)。

• 只要一直这么选下去,就能得出最终的解,每一步都是当下(子问题)的最优解,结果是原问题的最优解,这叫做最优子结构。

• 更书面的说法:如果问题的一个最优解中包含了子问题的最优解则该问题具有最优子结构。

• 具备这类结构的问题,可以用局部最优解来推导全局最优解,可以认为是一种剪枝法,是对"dfs遍历法”的优化。

• 贪心:由上一步的最优解推导下一步的最优解,而上一步之前的(历史)最优解则不作保留，区别动态规划，贪心是动态规划的特列。

二、动态规划

1、动态规划简介

什么是动态规划？

• 动态规划方法代表了这一类问题(最优子结构or子问题最优性)的一般解法,是设计方法或者策略,不是具体算法。
• 本质是递推,核心是找到状态转移的方式,写出dp方程。
• 善于解决重叠子问题，同级子问题有交叉部分。
• 形式：
  • 记忆型递归
  • 递推

2、背包问题

• 遇见一个物品有两站情况：要或者不要(还要考虑能不能装的下)。

  要的话：v2 = dfs(i+1,ww)；

  不要的话：v1 = v[i]+dfs(i+1,ww-w[i]);

  取v1和v2的最大值。

• 这是所有的情况：

• dp表：

  当前物品要的话：yao = v[i]+dp[i-1][j-w[i]]；
  当前物品不要的话：buyao = dp[ i-1][j];

package 动态规划;//背包问题import java.util.Arrays;/*** 有n个重量和价值分别为wi, vi的物品，从这些物品中挑选出总重量不超过M的物品，求所有挑选方案中价值总和的最大值。* 1<=n<=100* 1<=wi, vi<=100* 1<=W<=10000** 输入:* n=4* (w,v)={(2,3),(1,2),(3,4),(2,2)}* W=5* 输出:* 7 (选择第0, 1, 3号物品)** 因为对每个物品只有选和不选两种情况，所以这个问题称为01背包。*/
public class Demo01 {static int[] w = {2,1,3,2};//重量表static int[] v = {3,2,4,2};//价值表static int n = 4;//物品数量static int W = 5;//背包的承受极限static int[][] rec;public static void main(String[] args) {//一。dfsint ww = W;int ans = dfs(0,ww);System.out.println(ans);//二。记忆型递归rec = new int[n][W+1];for (int i = 0; i < n; i++) {Arrays.fill(rec[i],-1);}int ans2 = dfs2(0,ww);System.out.println(ans2);//三。背包之dp解法System.out.println(dp());}//一。dfsprivate static int dfs(int i,int ww){if (ww<=0) return 0;   //装不进去。if (i==n) return 0;   //没东西可选了。//有两种选择：装或者不装当前物品。int v2 = dfs(i+1,ww);   //不选择当前物品。if (ww>=w[i]){int v1 = v[i]+dfs(i+1,ww-w[i]);   //选择当前物品。return Math.max(v1,v2);}else {return v2;}}//二。记忆型递归private static int dfs2(int i,int ww){if (ww<=0) return 0;   //装不进去。if (i==n) return 0;   //没东西可选了。//1.计算之前先查询if (rec[i][ww]>=0){return rec[i][ww];}//有两种选择：装或者不装当前物品。int v2 = dfs(i+1,ww);   //不选择当前物品。int ans2;if (ww>=w[i]){int v1 = v[i]+dfs(i+1,ww-w[i]);   //选择当前物品。ans2 = Math.max(v1,v2);}else {ans2 = v2;}//2。计算之后在记录rec[i][ww] = ans2;return ans2;}//三。背包之dp解法，画表。private static int dp(){int[][] dp = new int[n][W+1];//初始化dp表的第一行for (int i = 0; i < W + 1; i++) {if (i>=w[0]){   //每种容量-0号物品。dp[0][i] = v[0];   //要得起}else {dp[0][i] = 0;   //要不起}}//其它行for (int i = 1; i < n; i++) {//j是列，也是背包的剩余容量for (int j = 0; j < W + 1; j++) {if (j>=w[i]){   //要得起//选择要或者不要这好物品。int yao = v[i]+dp[i-1][j-w[i]];//选择当前物品即i号物品，剩余容量。int buyao = dp[i-1][j];dp[i][j] = Math.max(yao,buyao);}else {dp[i][j] = dp[i-1][j];//要不起}}}return dp[n-1][W];//得到最终的价值。}
}

3、钢条切割问题

• dp表：vs[i] = Math.max(p[j-1]+vs[i-j],vs[i]);

• 每次循环把钢条分为两段：一段为整段（不再切了），一段为还要继续切割的一段。每次循环取最大的vs[i].

package 动态规划;//钢条切割问题import java.util.Arrays;/*** Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。* 假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。** 钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。* 注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。* 下面另n=10，给出个长度的价格，求价值最大值：* 长度i：	1	2	3	4	5	6	7	8	9	10* 价格Pi：	1	5	8	16	10	17	17	20	24	30*/
public class Demo02 {static int n =10;static int[] p = {1, 5, 8, 16, 10, 17, 17, 20, 24, 30};static int[] vs = new int[n + 1];public static void main(String[] args) {//记忆性递归Arrays.fill(vs,-1);System.out.println(r(n));//动态规划System.out.println(dp());}//动态规划private static int dp(){vs[0] = 0;for (int i = 1; i <= n; i++) {   //拥有的钢条长度。for (int j = 1; j <= i; j++) {   //保留j为整段。vs[i] = Math.max(p[j-1]+vs[i-j],vs[i]);}}return vs[n];}//记忆性递归private static int r(int x){if (x==0){return 0;}int ans = 0;for (int i = 1; i<=x; i++) {//1.计算前查询。if (vs[x-i] == -1){   //vs[x-i]是还要继续分割的那段。vs[x-i] = r(x-i);}int v = p[i-1]+vs[x-i];  //p[i-1]是保留的整段。ans = Math.max(v,ans);}//2.计算后赋值。vs[x] = ans;return ans;}}

4、数字三角形

• dp：dp[k][l] = triangle[k][l]+Math.max(dp[k+1][l],dp[k+1][l+1]);

  (dp[i][j]的值为下方的值+右下方的值)

• 递归和记忆型递归都是自顶向下，dp是自底向上的。

• 为了节约空间，可以使用滚动数组（用一维数组，不影响计算的情况下逐渐覆盖）。

package 动态规划;//数字三角形import java.util.Scanner;/*** 在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。* 路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。** ​7* 3 8* 8 1 0* 2 7 4 4* 4 5 2 6 5** 输入值：* 第一行包含一个整数N：三角形中的行数。接下来的N行描述了三角形的数据。三角形的行数大于1小于等于100，数字为 0 - 99。* 输出量：* 输出最大和。** 样本输入：* 5* 7* 3 8* 8 1 0* 2 7 4 4* 4 5 2 6 5* 样本输出：* 30*/
public class Demo03 {public static void main(String[] args) {Scanner scannr=new Scanner(System.in);int N=scannr.nextInt();int[][] triangle = new int[N][];for (int i = 0; i < N; i++) {triangle[i] = new int[i+1];for (int j = 0; j <i+1; j++) {triangle[i][j]=scannr.nextInt();}}//递归和记忆型递归都是自顶向下，dp是自底向上的。System.out.println(max01(triangle,0,0));System.out.println(max02(triangle,0,0));System.out.println(max03(triangle,0,0));}//递归public static int max01(int[][] triangle,int i,int j){int row = triangle.length;if (i == row-1){   //最后一行。return triangle[i][j];}else {//顶点的值+max（左侧支线的最大值，右侧支线的最大值）return triangle[i][j]+Math.max(max01(triangle,i+1,j),max01(triangle,i+1,j+1));}}//动态规划public static int max02(int[][] triangle,int i,int j){int row = triangle.length;   //行数。int column = triangle[row-1].length;   //最后一列的烈数。int[][] dp = new int[row][column];for (int k = 0; k < column; k++) {dp[row-1][k] = triangle[row-1][k];   //初始化最后一行。}//倒第二行开始计算。for (int k = row-2; k >=0; k--) {//第几行就有几个数。for (int l = 0; l <=k; l++) {//该值为当前位置的值加上下面两个的最大值。dp[k][l] = triangle[k][l]+Math.max(dp[k+1][l],dp[k+1][l+1]);}}return dp[0][0];}//滚动数组：用一维数组，不影响计算的情况下逐渐覆盖。可以节省空间。public static int max03(int[][] triangle,int i,int j){int row = triangle.length;   //行数。int column = triangle[row-1].length;   //最后一列的烈数。int[] dp = new int[column];for (int k = 0; k < column; k++) {dp[k] = triangle[row-1][k];   //初始化最后一列。}for (int k = row-2; k >=0; k--) {for (int l = 0; l <=k; l++) {dp[l] = triangle[k][l]+Math.max(dp[l],dp[l+1]);}}return dp[0];}}

5、最长公共子序列

• dp表：如果s1和s2当前的字符串相同的话，dp[i][j]=dp[i-1][j-1]+1;否则dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);

package 动态规划;//最长公共子序列import java.util.ArrayList;
import java.util.Scanner;/*** 求最大公共子序列问题。* 输入：* AB34C* A1BC2* 输出为为：* ABC* 更多案例请看测试用例。*/
public class Demo04 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();System.out.println(dfs(s1,s2));System.out.println(dp(s1,s2));}//dfsprivate static ArrayList<Character> dfs(String s1,String s2){int len1 = s1.length();int len2 = s2.length();ArrayList<Character> ans = new ArrayList<>();for (int i = 0; i < len1; i++) {//求以i字符开头的公共子序列。ArrayList<Character> list = new ArrayList<>();//和s2的每个字符比较。for (int j = 0; j < len2; j++) {if (s1.charAt(i)==s2.charAt(j)){   //如果相等。list.add(s1.charAt(i));//addAll() 方法将给定集合中的所有元素添加到 arraylist 中。list.addAll(dfs(s1.substring(i+1),s2.substring(j+1)));break;}}if (list.size()>ans.size()){ans=list;}}return ans;}//dpprivate static String dp(String s1,String s2){int len1 = s1.length();int len2 = s2.length();int[][] dp = new int[len1+1][len2+1];//动归数组int flag = 0;//初始化第一列；//O(M)for (int i = 1; i <=len1; i++) {//出现了一个flag = 1；后面全是1。if (flag == 1){dp[i][1] = 1;}else if (s2.charAt(i-1)==s1.charAt(0)){dp[i][1] = 1;flag = 1;}else {dp[i][1] = 0;}}flag = 0;//初始化第一行；//O(N)for (int j = 1; j <=len2 ; j++) {//出现了一个flag = 1；后面全是1。if (flag == 1){dp[1][j] = 1;}else if (s1.charAt(j-1)==s2.charAt(0)){dp[1][j] = 1;flag = 1;}else {dp[1][j] = 0;}}//O(M*N)for (int i = 2; i<=len1; i++) {   //Mfor (int j = 2; j<=len2; j++) {   //Nint maxOfLeftAndUp = Math.max(dp[i-1][j],dp[i][j-1]);if (s1.charAt(i-1)==s2.charAt(j-1)){//dp[i][j]=Math.max(maxOfLeftAndUp,dp[i-1][j-1]+1);dp[i][j]=dp[i-1][j-1]+1;}else {dp[i][j] = maxOfLeftAndUp;}}}//解析动态规划表，得到最长公共子序列。return parseDp(dp,s1,s2);}private static String parseDp(int[][] dp,String s1,String s2){int M = s1.length();int N = s2.length();StringBuilder sb = new StringBuilder();while (M>0 && N>0){//比左上的元素大1，一定是当前位置的字符串相等。if (dp[M][N] > Math.max(dp[M-1][N],dp[M][N-1])){sb.insert(0,s1.charAt(M-1));   //在0位置插入元素。M--;N--;}else {    //一定选择的是左边和上边的大者得到的。if (dp[M-1][N] > dp[M][N-1]){   //由上边得到的M--;   //往上移}else {    //由左边得到的N--;   //往左移}}}return sb.toString();}
}

6、完全背包问题

• dp:dp[i][j] = Math.max(dp[i-1][j],(vi[i]+dp[i-1][j-wi[i]]));(装或者没装)

package 动态规划;//完全背包问题
//这个题是自己写的，不知道对不对。import java.util.Scanner;/*** 有N种物品和一个最大承受重量为W的背包，每种物品都有无限件可用。第i种物品的体积是wi，价值是vi。* 现在请你选取一些物品装入背包，使这些物品的体积总和不超过背包容量，且价值总和最大。** Input:* 第一行输出两个数N,W，分别表示物品种类数和背包能装的总重量；1≤N≤100，1≤V≤50000。* 之后N行，每行两个数wi,vi，分别表示第i种物品的重量和价值；1≤vii,cii≤10000。* Output:* 输出一个数，表示最大的价值.** Sample Input:* 2 11* 2 3* 6 14* Sample Output:* 20*/
public class Demo05 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int N=sc.nextInt();   //N为物品的种类。int W=sc.nextInt();   //能装的总重量。int[] wi = new int[N];int[] vi = new int[N];for (int i = 0; i < N; i++) {wi[i] = sc.nextInt();vi[i] = sc.nextInt();}sc.close();int[][] dp = new int[N][W+1];//初始化第一行。for (int j = 0; j <= W; j++) {dp[0][j] = j/wi[0]*vi[0];}for (int i = 1; i < N; i++) {for (int j = wi[i]; j <= W; j++) {dp[i][j] = Math.max(dp[i-1][j],(vi[i]+dp[i-1][j-wi[i]]));}}System.out.println(dp[N-1][W]);}
}

7、最长递增子序列

• dp表：

• 往前面找比arr[i]小的，如果存在，dp[i]为所有小于它的值加一（dp[i]+1）的最大值；如果没有一个小于它，它只能为1。

package 动态规划;//最长递增子序列/*** 给定一个无序的整数数组，找到其中最长上升子序列的长度。** 示例:* 输入: [10,9,2,5,3,7,101,18]* 输出: 4* 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。*/
public class Demo06 {public static void main(String[] args) {int[] arr = {4,2,3,1,5,6};System.out.println(dp(arr));System.out.println(f(arr));System.out.println(dp2(arr));}//dpprivate static int dp(int[] arr){int[] dp = new int[arr.length];dp[0]=1;//遍历这个数组。for (int i = 1; i < arr.length; i++) {int count = 1;//使这个数组的每个元素跟前面的元素做比较。for (int j = i-1; j >=0; j--) {if (arr[i]>arr[j]){count = Math.max(count,dp[j]+1);}}dp[i] = count;}//找到最大的。int ans = 1;for (int i = 0; i < dp.length; i++) {ans = Math.max(ans,dp[i]);}return ans;}//暴力法private static int f(int[] arr){int maxCount = 0;//分别让每个元素为最长子序列的开头。for (int i = 0; i < arr.length; i++) {int p = i;int cnt = 1;for (int j = i+1; j < arr.length; j++) {if (arr[j]>arr[p]){cnt++;p=j;}}maxCount = Math.max(maxCount,cnt);}return maxCount;}//dp之经典法private static int dp2(int[] arr){int[] dp = new int[arr.length+1];dp[1] = arr[0];   //长度为1的最长递增子序列，初始化为第一个元素。int p =1;   //记录dp更新的最后位置。(下标)for (int i = 1; i < arr.length; i++) {if (arr[i]>dp[p]){dp[p+1] = arr[i];p++;}else {for (int j = 1; j <=p; j++) {//把比它大的元素替换掉。if (dp[j]>arr[i]){dp[j]=arr[i];}}}}//下标作为返回结果。return p;}
}

8、小结

• 动态规划用于解决多阶段决策最优化问题。

• 三要素：

  • 阶段
  • 状态
  • 决策

• 两个条件:

  • 最优子结构(最优化原理)： 当前状态的决策依赖于历史上以前子问题决定。
  • 无后效性：当前状态是前面状态的完美总结，后面的状态由前面决定，现在的状态不会影响历史状态。

动态解题的一般思路：

• 是否可以用动态规划,否则用搜索。

  • 模型匹配:多做题，掌握经典模型。

    • 一维:上升子序列模型，背包模型。
    • 二维:最长公共子序列问题。

  • 寻找规律:规模由小到大,或者由大到小，做逐步分析。

  • 放宽条件或增加条件。

• 一般过程：

  • 找到过程演变中变化的量(状态)，以及变化的规律(状态转移方程)。
  • 确定一些初始状态，通常需要dp数组来保存。
  • 利用状态转移方程，推出最终答案。

• 解法：

  • 自顶向下，记录递归；如果有重叠子问题，带备忘录。
  • 自底向上，递推。

贪心和动规：

• 可以用局部最优解来推导全局最优解,即动态规划。
• 贪心：这一阶段的解,由上一阶段直接推导出。
• 动规：当前问题的最优解,不能从上一阶段子问题简单得出，由前面多阶段多层子问题共同计算出,因此需要保留历史上求解过的子问题及其最优解。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！