六.分治法与动态规划
主要内容:
①分治思想的重要性
②二分法是基础
③动态规划问题的求解次序
④复杂问题的规划
递归:分成小规模的问题(一个小,一个大)
分治:主要是二分法
1. 二分查找
已知有序的序列,比如:2,3,3,5,9,9,9,12,12,13,15,22,22,22,22,25,25,23,91,95有整数x,比如: x=23
要求找到一个刚好比x稍微大一点的元素位置
当数组较大的时候,需要二分查找加快速度。
【源代码】
【JAVA:于航】
public class A
{
// 含有begin, 不含end
static int f(int[] a, int begin, int end, int x){
if(end-begin==1){//出口
if(a[begin] > x) return begin;
return end;
}
int k = (begin+end)/2;//二分
if(x>=a[k]) return f(a,k,end,x);
return f(a,begin,k,x);
}
// 求x应该插入的位置
// return 刚好比x稍微大点的那个数的位置
static int f(int[] a, int x){
if(x>=a[a.length-1]) return -1;
return f(a,0,a.length,x);
}
public static void main(String[] args){
int[] a = {1,5,11,24,25,32,32,33,49,66,68,69,70
,75,88,102,114,119,120,135,146,221,294,300,302,305,333};
System.out.println(f(a,32));
}
}
2. 最大序列和
数组中整数有正有负求一连续子段,使得和最大化
例如:
2,4,-7,5,2,-1,2,-4,3
最大连续段:
5,2,-1,2
其最大和为8
左右两个区间,如何处理分界问题
|__________________________|_________________________|
a <——c——> b
【JAVA:于航】
public class A
{
static int f(int[] a, int begin, int end){
if(end-begin==1){ // 由于是开区间:[begin,end)
if(a[begin] > 0) return a[begin];
return 0;
}
int k = (begin+end)/2;
int t1 = f(a,begin,k);//注意:左边的数组中,没有k元素
int t2 = f(a,k,end);
int t3a = 0;
int sum = 0;
for(int i=k-1; i>=begin; i--){
sum += a[i];
if(sum > t3a) t3a = sum;
}
int t3b=0;
sum = 0;
for(int i=k; i<end; i++){ sum += a[i]; if(sum > t3b) t3b = sum;
}
int t3 = t3a + t3b;
int max = 0;
if(t1 > max) max = t1;
if(t2 > max) max = t2;
if(t3 > max) max = t3;
return max;
}
static int work(int[] a){//二分法的做法
return f(a,0,a.length);
}
public static void main(String[] args){
System.out.println(work(new int[]{2,4,-7,5,2,-1,2,-4,3}));
}
}
3. 大数乘法问题
用串的形式表示大数的乘法。即求类似: “23234845847839461464158174814792” * “6457847285617487843234535”
要求结果返回一个串。
【源代码】
【JAVA:于航】
public class A
{
static String zero(int n){
if(n==0) return "";
if(n==1) return "0";
return zero(n/2) + zero(n/2) + zero(n%2);
}
static String add(String a, String b){
if(a.length()<=8 && b.length()<=8)
return Integer.parseInt(a) + Integer.parseInt(b) + "";
String a1 = "0"; String a2 = a; if(a.length()>8){
a1 = a.substring(0,a.length()-8);a2 = a.substring(a.length()-8);
}
String b1 = "0";
String b2 = b;
if(b.length()>8){
b1 = b.substring(0,b.length()-8);
b2 = b.substring(b.length()-8);
}
String t = add(a2,b2);
while(t.length()<8) t = "0" + t;//进位:必然进一位
if(t.length()>8)
return add(add(a1,b1),"1") + t.substring(1);//把t中的进位甩掉,加到前面
return add(a1,b1) + t;}
static String multi(String a, String b){
if(a.length()<=4 && b.length()<=4) return Integer.parseInt(a) * Integer.parseInt(b) + ""; if(a.length()>4){
int k = a.length()/2;
String a1 = a.substring(0,k);
String a2 = a.substring(k);
return add(multi(a1,b)+zero(a2.length()),multi(a2,b));
}
return multi(b,a);
}
public static void main(String[] args){
System.out.println(multi("1234567890987654321666",
"1234567890123456789555"));
System.out.println(new BigInteger("1234567890987654321666")
.multiply(new BigInteger("1234567890123456789555")));
}
}
4. 提速
取球博弈和振兴中华等的递归解法有个弱点:规模变大后,迅速超时…
解决方案:
1. 缓存子调用,把已经调用过的存在map中。
2. 不用递归,巧妙设计计算次序,使用数组存结果
【源代码】
【JAVA:于航】
//取球问题
public class A
{
// n: 球数
// return: true必赢
static boolean f(int n){
if(n==0) return true;
if(n >= 1 && f(n-1)==false) return true;
if(n >= 3 && f(n-3)==false) return true;
if(n >= 7 && f(n-7)==false) return true;
if(n >= 8 && f(n-8)==false) return true;
return false;
}
public static void main(String[] args){
System.out.println(f(55));
}
}
// 缓存法
import java.util.*;
public class B
{
static Map map = new HashMap();
// n: 球数
// return: true必赢
static boolean f(int n){
if(map.get(n)!=null) return (Boolean)map.get(n);
boolean t = false;
if(n >= 1 && f(n-1)==false) t = true;
if(n >= 3 && f(n-3)==false) t = true;
if(n >= 7 && f(n-7)==false) t = true;
if(n >= 8 && f(n-8)==false) t = true;
map.put(n,t);
return t;
}
public static void main(String[] args){
map.put(0,true);
System.out.println(f(1055));
}
}
//振兴中华
public class AA
{
static int f(int m, int n)
{
if(m==1 || n==1) return 1;
return (f(m-1,n) + f(m,n-1)) % 10000;//避免越界
}
public static void main(String[] args)
{
System.out.println(f(20,15));
//System.out.println(f(3,2));
}
}
public class BB
{
static int f(int m, int n)
{
if(m==1 || n==1) return 1;
return (f(m-1,n) + f(m,n-1)) % 10000;
}
public static void main(String[] args)
{
int[][] a = new int[100][100];
for(int i=1; i<100; i++){
a[i][1] = 1;
a[1][i] = 1;
}
for(int i=2; i<100; i++){
for(int j=2; j<100; j++){
a[i][j] = (a[i-1][j] + a[i][j-1]) % 10000;
}
}
System.out.println(a[20][15]);
System.out.println(f(20,15));
}
}
5. 城墙刷漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如图所示)现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)
比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。
输入数据为一个正整数(不大于1000)
输出数据为一个正整数。
例如:
用户输入:
2
程序应该输出:
24
再例如:
用户输入:
3
程序应该输出:
96
再例如:
用户输入:
22
程序应该输出:
359635897
锦囊:
1. fb(n) 从边缘某格开始,到与它相邻的另一个边缘格子结束
fb(n) = fb(n-1) * 2
2. fa(n) 从某个边缘格子开始的所有情况fa(n) = fb(n) + 2*fa(n-1) + 4 * fa(n-2)
最后走相邻边缘格 第1步走相邻边缘格 第2步走相邻边缘格
对面格子只有三种情况:①第一步就走 ②第二步走 ③最后一步走 ,否则就来不及了
3. fk(i,n) 一共有n个格子,从中间的第i个格子为起点,任意结束fk(i,n) = ( fb(i)*fa(n-i)*2 + fb(n-i+1)*fa(i-1)*2 ) * 2
先走左边再右边 先走右边再左边 有两个可能起点
因此: 总情况包含:从某个边缘格开始的所有情况 4 * fa(i)
从中间某个格子开始的所有情况 i从2到n-1求和:fk(i,n)
【JAVA:于航】
public class A
{
static long MM = 1000000007;
// 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
static long fb(int n)
{
if(n==1) return 1;
return fb(n-1) * 2 % MM;
}
// 从某个边缘格子开始的所有情况
static long fa(int n)
{
if(n==1) return 1;
if(n==2) return 6;
return (2 * fa(n-1) + 4 * fa(n-2) + fb(n)) % MM;
}
// 规模为n的问题之中间第i格
static long fk(int i, int n)
{
//return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了(即左边与右边的情况*2)
return (fb(i)*fa(n-i)*2 % MM + fb(n-i+1)*fa(i-1)*2 % MM) * 2 % MM;
}
static long f(int n)
{
if(n==1) return 2;
long sum = fa(n) * 4 % MM;
for(int i=2; i<n; i++){
sum = (sum + fk(i,n)) % MM;
}
return sum;
}
public static void main(String[] args)
{
for(int i=1; i<30; i++){
System.out.println(i + ": " + f(i));
}
}
}
public class B
{
static long M = 1000000007;
// 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
static long[] fb = new long[1000];
// 从某个边缘格子开始的所有情况
static long[] fa = new long[1000];
// 规模为n的问题之中间第i格
static long fk(int i, int n)
{
//return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
return (fb[i]*fa[n-i]*2 % M + fb[n-i+1]*fa[i-1]*2 % M) * 2 % M;
}
static long f(int n)
{
if(n==1) return 2;
long sum = fa[n] * 4 % M;
for(int i=2; i<n; i++){
sum = (sum + fk(i,n)) % M;
}
return sum;
}
public static void main(String[] args)
{
fb[1] = 1;
for(int i=2; i<fb.length; i++){
fb[i] = fb[i-1] * 2 % M;
}
fa[1] = 1;
fa[2] = 6;
for(int i=3; i<fa.length; i++){
fa[i] = (2*fa[i-1] + 4 * fa[i-2] + fb[i]) % M;
}
for(int i=1; i<130; i++){
System.out.println(i + ": " + f(i));
}
}
}
6. 环形涂色
如上图,组成环形的格子需要涂3种颜色。
它们的编号分别是1~14
相邻的格子不能用相同的颜色。
涂色方案的数目是:24576
当格子数目为50的时候,求涂色方案总数。
【源代码】
【JAVA:于航】
public class A
{
/*
static long f(int n){
if(n==1) return 3;
if(n==2) return 6;
return 2 * f(n-2) + f(n-1);
}
*/
public static void main(String[] args){
long[] f = new long[50+10];
f[1] = 3;
f[2] = 6;
for(int i=3; i<=50; i++){
f[i] = f[i-2] * 2 + f[i-1];
//①第二个与第n个同色时,第一个可以涂两种颜色 ②第二个与第n个不同色时,第一个可以涂一种颜色
}for(int i=3; i<=50; i++){
System.out.println(i + ": " + f[i]);
}
}
}