算法笔记（二）：动态规划

- 日理万妓 2022-12-18 13:54 362阅读 0赞

# 一、基本思想 #

动态规划与分治法由相似之处，动态规划在求解子问题时也需要将原问题分解为子问题，首先求子问题的解，然后在此基础上求解原问题的解。然而，分治法中子问题与与原问题的性质相同并且相互独立，而动态规划产生的子问题是**相互重叠的并非相互独立**。因此，如果使用分治法求解子问题就需要重复计算很多子问题导致运算效率降低。而动态规划采取了一种策略，即在求解子问题时一旦得到这个子问题就记录到一个表格中而不是丢弃，未来一旦需要用到这个子问题的解只需回到表格中以常数时间获取这个子问题的解即可，是一种**自底向上**的求解方式，具有较高的效率。例如，计算斐波那契数列时，采用递归算法算f第5项元素f(5)，则需要计算出第四项f(4)和第三项f(3)，而算f(4)时又需要算出f(3)和f(2)，算完后递归返回继续算f(3)，由于f(3)结果没有保存就被重复计算了，这就是子问题重叠问题。如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center]

# 二、基本要素 #

能用动态规划求解的问题具备的两个基本性质：最优子结构和子问题重叠性质。这两个性质也是判断一个问题是否可以用动态求解的标准。其基本步骤是：  
1、分析问题的最优解性质，刻画最优解的结构特征；  
2、建立最优值的递归定义；  
3、以自底向上的方式计算出最优值；  
4、构造问题的最优解。

# 三、经典案例 #

### 矩阵连乘 ###

假设A是一个p × \\times ×q的矩阵，B是一个q × \\times ×r的矩阵，两个矩阵相乘共用了p × \\times ×q × \\times ×r次乘法。由于矩阵乘法满足结合律，因此计算矩阵连乘积的计算次序有多种。此处用动态规划求解使得乘法次数最少(计算机中的乘法操作较为复杂)的矩阵连乘计算次序。

#### 步骤 ####

**1、找出最优解的性质并刻画其结构特征**  
1）将矩阵连乘积AiAi+1…Aj简记为A\[i:j\]，i<=j，Ai的维数为pi-1pi。  
2）考察A\[i:j\]的最优计算次序。设在Ak和Ak+1之间将连乘矩阵断开,i<=k<j，相应的矩阵加括号的方式为(AiAi+1…Ak)(Ak+1Ak+2…Aj)。  
3）计算量：A\[i:k\]的计算量加上A\[k+1:j\]的计算量再加上A\[i:k\]和A\[k+1:j\]相乘的计算量。  
**2、建立递归关系**

假设计算A\[i:j\]的最少数乘次数为 m\[i\]\[j\]。  
1）当i=j时，矩阵为单一矩阵，无需计算，m\[i\]\[i\]=0。  
2）当i<j时，可以利用最优子结构性质来计算m\[i\]\[j\]。假设计算A\[i:j\]的最优计算次序在Ak和Ak+1之间断开，则m\[i\]\[j\]可以递归定义为  
 T ( n ) = \{ 0 , i = j m i n \[ m \[ i \] \[ k \] + m \[ k + 1 \] \[ j \] + p i − 1 p k p j \] i < j T(n)=\\left\\\{ \\begin\{array\}\{lcl\} 0, & & \{i = j\}\\\\ min\[m\[i\]\[k\]+m\[k+1\]\[j\]+p\_\{i-1\}p\_\{k\}p\_\{j\}\] & & \{i <j\} \\end\{array\} \\right. T(n)=\{ 0,min\[m\[i\]\[k\]\+m\[k\+1\]\[j\]\+pi−1pkpj\]i=ji<j  
3）在计算过程中并不知道k的确定位置，但k的位置只有j-i种可能。  
3、应用举例。设有6个矩阵连乘A1A2A3A4A5A6。找出最优计算次序使得矩阵连乘所需的计算量最少。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 1]![在这里插入图片描述][20201027212303854.png_pic_center]

***第1步，长度r=1时，单一矩阵是完全加括号的***（一个矩阵连乘积的计算次序完全确定该矩阵就是完全加括号）。矩阵s用来记录加括号的位置：m\[1\]\[1\]=0，m\[2\]\[2\]=0，m\[3\]\[3\]=0，m\[4\]\[4\]=0，m\[5\]\[5\]=0，m\[6\]\[6\]=0；s\[1\]\[1\]=0，s\[2\]\[2\]=0，s\[3\]\[3\]=0，s\[4\]\[4\]=0，s\[5\]\[5\]=0，s\[6\]\[6\]=0。结果如图 ：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 2]***第2步，r=2时计算两个矩阵连乘的最优值。***  
i=1,j=2时，计算A1A2：  
m\[1\]\[2\]=m\[1\]\[1\]+m\[2\]\[2\]+p\[0\]p\[1\]p\[2\]=15750；s\[1\]\[2\]=1  
i=2,j=3时，计算A2A3：  
m\[2\]\[3\]=m\[2\]\[2\]+m\[3\]\[3\]+p\[1\]p\[2\]p\[3\]=2625；s\[2\]\[3\]=2  
i=3,j=4时，计算A3A4：  
m\[3\]\[4\]=m\[3\]\[3\]+m\[4\]\[4\]+p\[2\]p\[3\]p\[4\]=750；s\[3\]\[4\]=3  
i=4,j=5时，计算A4A5：  
m\[4\]\[5\]=m\[4\]\[4\]+m\[5\]\[5\]+p\[3\]p\[4\]p\[5\]=1000；s\[4\]\[5\]=4  
i=5,j=6时，计算A5A6：  
m\[5\]\[6\]=m\[5\]\[5\]+m\[6\]\[6\]+p\[4\]p\[5\]p\[6\]=5000；s\[5\]\[6\]=5  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 3]***第3步，r=3时计算三个矩阵连乘的最优值。***  
i=1，j=3时，计算A1A2A3：  
k=1时，m\[1\]\[3\]=m\[1\]\[1\]+m\[2\]\[3\]+p\[0\]p\[1\]p\[3\]=7875；  
k=2时，m\[1\]\[3\]=m\[1\]\[2\]+m\[3\]\[3\]+p\[0\]p\[2\]p\[3\]=18000；  
m\[1\]\[3\]=7875；s\[1\]\[3\]=1  
i=2，j=4时，计算A2A3A4：  
k=2时，m\[2\]\[4\]=m\[2\]\[2\]+m\[3\]\[4\]+p\[1\]p\[2\]p\[4\]=6000；  
k=3时，m\[2\]\[4\]=m\[2\]\[3\]+m\[4\]\[4\]+p\[1\]p\[3\]p\[4\]=4375；  
m\[2\]\[4\]=4375；s\[2\]\[4\]=3  
i=3，j=5时，计算A3A4A5：  
k=3时，m\[3\]\[5\]=m\[3\]\[3\]+m\[4\]\[5\]+p\[2\]p\[3\]p\[5\]=2500；  
k=4时，m\[3\]\[5\]=m\[3\]\[4\]+m\[5\]\[5\]+p\[2\]p\[4\]p\[5\]=3750；  
m\[3\]\[5\]=2500；s\[3\]\[5\]=3  
i=4，j=6时，计算A4A5A6：  
k=4时，m\[4\]\[6\]=m\[4\]\[4\]+m\[5\]\[6\]+p\[3\]p\[4\]p\[6\]=6250；  
k=5时，m\[4\]\[6\]=m\[4\]\[5\]+m\[6\]\[6\]+p\[3\]p\[5\]p\[6\]=3500；  
m\[4\]\[6\]=3500；s\[4\]\[6\]=5  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 4]***第4步，r=4时计算四个矩阵连乘的最优值。***  
i=1，j=4时计算A1A2A3A4：  
k=1，m\[1\]\[4\]=m\[1\]\[1\]+m\[2\]\[4\]+p\[0\]p\[1\]p\[4\]=14875；  
k=2，m\[1\]\[4\]=m\[1\]\[2\]+m\[3\]\[4\]+p\[0\]p\[2\]p\[4\]=21000；  
k=3，m\[1\]\[4\]=m\[1\]\[3\]+m\[4\]\[4\]+p\[0\]p\[3\]p\[4\]=9375；  
m\[1\]\[4\]=9375，s\[1\]\[4\]=3  
i=2，j=5时计算A2A3A4A5：  
k=2，m\[2\]\[5\]=m\[2\]\[2\]+m\[3\]\[5\]+p\[1\]p\[2\]p\[5\]=13000；  
k=3，m\[2\]\[5\]=m\[2\]\[3\]+m\[4\]\[5\]+p\[1\]p\[3\]p\[5\]=7125；  
k=4，m\[1\]\[4\]=m\[2\]\[4\]+m\[5\]\[5\]+p\[1\]p\[4\]p\[5\]=11375；  
m\[2\]\[5\]=7125，s\[1\]\[4\]=3  
i=3，j=6时计算A3A4A5A6：  
k=3，m\[3\]\[6\]=m\[3\]\[3\]+m\[4\]\[6\]+p\[2\]p\[3\]p\[6\]=5375；  
k=4，m\[3\]\[6\]=m\[3\]\[4\]+m\[5\]\[6\]+p\[2\]p\[4\]p\[6\]=9500；  
k=5，m\[3\]\[6\]=m\[3\]\[5\]+m\[6\]\[6\]+p\[2\]p\[5\]p\[6\]=10000；  
m\[3\]\[6\]=5375，s\[1\]\[4\]=3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 5]***第5步，r=5时计算五个矩阵连乘的最优值。***  
i=1,j=5时，计算A1A2A3A4A5：  
k=1,m\[1\]\[5\]=m\[1\]\[1\]+m\[2\]\[5\]+p\[0\]\[1\]\[5\]=28125;  
k=2,m\[1\]\[5\]=m\[1\]\[2\]+m\[3\]\[5\]+p\[0\]\[2\]\[5\]=27250;  
k=3,m\[1\]\[5\]=m\[1\]\[3\]+m\[4\]\[5\]+p\[0\]\[3\]\[5\]=11875;  
k=4,m\[1\]\[5\]=m\[1\]\[4\]+m\[5\]\[5\]+p\[0\]\[4\]\[5\]=15375;  
m\[1\]\[5\]=11875，s\[1\]\[5\]=3  
i=2,j=6时，计算A2A3A4A5A6：  
k=2,m\[2\]\[6\]=m\[2\]\[2\]+m\[3\]\[6\]+p\[1\]\[2\]\[6\]=13125;  
k=3,m\[2\]\[6\]=m\[2\]\[3\]+m\[4\]\[6\]+p\[1\]\[3\]\[6\]=10500;  
k=4,m\[2\]\[6\]=m\[2\]\[4\]+m\[5\]\[6\]+p\[1\]\[4\]\[6\]=18075;  
k=5,m\[2\]\[6\]=m\[2\]\[5\]+m\[6\]\[6\]+p\[1\]\[5\]\[6\]=24625;  
m\[2\]\[6\]=10500，s\[2\]\[6\]=3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 6]***第6步，r=6时计算六个矩阵连乘的最优值。***  
i=1，j=6时计算A1A2A3A4A5A6：  
k=1,m\[1\]\[6\]=m\[1\]\[1\]+m\[2\]\[6\]+p\[0\]\[1\]\[6\]=36750;  
k=2,m\[1\]\[6\]=m\[1\]\[2\]+m\[3\]\[6\]+p\[0\]\[2\]\[6\]=32375;  
k=3,m\[1\]\[6\]=m\[1\]\[3\]+m\[4\]\[6\]+p\[0\]\[3\]\[6\]=15125;  
k=4,m\[1\]\[6\]=m\[1\]\[4\]+m\[5\]\[6\]+p\[0\]\[4\]\[6\]=21875;  
k=5,m\[1\]\[6\]=m\[1\]\[5\]+m\[6\]\[6\]+p\[0\]\[5\]\[6\]=26875;  
m\[1\]\[6\]=15125，a\[1\]\[6\]=3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 7]至此，算法结束，六个矩阵连乘最优值是15125。  
**Java代码实现：**

public class MatricChain { 
    	static int n = 6;
    	public static void main(String[] args) { 
    		int[] p = { 30,35,15,5,10,20,25};
    		int[][] m = new int[n+1][n+1];
    		int[][] s = new int[n+1][n+1];
    		matrixChain(p,m,s);
    		traceback(s,1,6);
    		System.out.println("最优计算次数："+m[1][n]);
    	}
    
    	public static void matrixChain (int []p, int [][]m, int [][]s){     
    		for (int i = 1; i <= n; i++) { 
    			m[i][i] = 0;
    		}
    		for (int r = 2; r <= n; r++) { 
    			for (int i = 1; i <= n - r+1; i++) { 
    				int j=i+r-1;
    				//System.out.println(i+":"+j);
    				m[i][j] = m[i][i] +m[i+1][j]+ p[i-1]*p[i]*p[j];
    				s[i][j] = i;
    				for (int k = i+1; k < j; k++) { 
    					int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
    					if (t < m[i][j]) {  
    						m[i][j] = t;
    						s[i][j] = k;
    					}
    				}
    			} 
    		}
    	}
    	
    	public static void traceback(int [][]s,int i,int j)
    	  { 
    	    if(i==j)return;
    	      traceback(s,i,s[i][j]);
    	      traceback(s,s[i][j]+1,j);
    	      System.out.println("Multiply A["+i+":"+s[i][j]+"] and A["+(s[i][j]+1)+":"+j+"]");
    	  }
    }

# 四、相关题目 #

# 01背包 #

/* * 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中总价值最大的值 * 输入 * n = 4 * (w, v) = {(2,3), (1,2), (3,4), (2,2)} * W = 5 * * 输出 * 7（选择第0,1,3号物品） * * 因为对于每个物品只有选和不选两种情况，所以这个问题也叫01背包 */
    public class _01背包 { 
    	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) { 
    		int ww = W;//创建总重量W的副本，保留W的值不变
    		int ans = dfs(0, ww);
    		System.out.println(ans);
    		
    		rec = new int[n][W + 1];
    		for(int i = 0; i < n; i++) { //将记录数组元素初始化为-1
    			Arrays.fill(rec[i], -1);
    		}
    		ww = W;
    		ans = m(0, ww);
    		System.out.println(ans);
    		
    		ww = W;
    		ans = dp(0, ww);
    		System.out.println(ans);
    	}
    	/* * 2^n的复杂度 */
    	public static int dfs(int i, int ww) {  //返回总价值
    		if(ww <= 0) //如果剩余的重量小于等于0，装不下，返回总价值0
    			return 0;
    		if(i == n) //如果没有物品了，返回总价值0
    			return 0;
    		int v2 = dfs(i+1, ww);//不选择当前物品
    		if(w[i] <= ww) { 
    			int v1 = v[i] + dfs(i+1, ww-w[i]); //选择当前物品
    			return Math.max(v1, v2);
    		}else { 
    			return v2;
    		}
    	}
    	/* * 记忆型递归 */
    	public static int m(int i, int ww) { 
    		if(ww <= 0) 
    			return 0;
    		if(i == n)
    			return 0;
    		
    		if(rec[i][ww] >= 0)
    			return rec[i][ww];
    		
    		int v2 = m(i+1, ww);//不选当前物品
    		int ans;
    		if(w[i] <= ww) { 
    			int v1 = v[i] + dfs(i+1, ww-w[i]); //选择当前物品
    			ans = Math.max(v1, v2);
    		}else { 
    			ans = v2;
    		}
    		rec[i][ww] = ans;
    		return ans;
    	}
    	
    	//dp(动态规划)解法，需要先建立一个dp表，表的最后一行最后一列的那个数就是答案
    	//思想与前面记忆型递归类似
    	public static int dp(int i, int ww) { 
    		int[][] dp = new int[n][W+1];
    		//初始化dp表的第一行，列的下标也代表剩余的容量
    		for(int k = 0; k < W+1; k++) { 
    			if(w[0] > k) { 
    				dp[0][k] = 0;
    			}else { 
    				dp[0][k] = v[0];
    			}
    		}
    		//其他行
    		for(int k = 1; k < n; k++) { 
    			for(int j = 0; j < W+1; j++) { 
    				if(w[k] <= j) { 
    					int v1 = v[k] + dp[k-1][j-w[k]];
    					int v2 = dp[k-1][j];
    					dp[k][j] = Math.max(v1, v2);
    				}else { 
    					dp[k][j] = dp[k-1][j];
    				}
    			}
    		}
    		return dp[n-1][W];
    	}
    }

# 背包问题一 #

/* * 给出n个物体，第i个物体重量为wi，选择尽量多的物体使得总量不超过c * 思路： * 将物体重量按从小到大排序后把较小的一个个装入背包，知道不超过重量c */
    public class _背包问题一 { 
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		int[] w = new int[n];
    		for(int i = 0; i<n; i++) { 
    			w[i] = sc.nextInt();
    		}
    		int c = sc.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 = c;
    		int cnt = 0;
    		for(int i = 0; i < n; i++) { 
    			if(w[i] <= sum) { 
    				sum -= w[i];
    				cnt++;
    			}
    		}
    		return cnt;
    	}
    }

# 部分背包 #

/* * 有n个物体，第i个物体的重量为wi，价值为vi，在总重量不超过c的情况下让总价值尽量高 * 每一个物体都可以只取走一部分，价值和重量按比例计算 */
    public class _部分背包 { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		//n个物体
    		int n = sc.nextInt();
    		//重量数组
    		double[] w = new double[n];
    		//价格数组
    		double[] v = new double[n];
    		//总重量
    		int c = sc.nextInt();
    		for(int i = 0; i < n; i++) { 
    			w[i] = sc.nextDouble();
    		}
    		for(int i = 0; i < n; i++) { 
    			v[i] = sc.nextDouble();
    		}
    		
    		double[] price = new double[n];
    		for(int i = 0; i < n; i++) { 
    			price[i] = v[i]/w[i]; 
    		}
    		sort(w, v, price);//按单价从高到底排序
    		int weight = c;
    		double maxValue = 0;
    		for(int i = 0; i < n; i++) { 
    			if(weight > 0) { 
    				if(w[i] <= weight) { 
    					weight -= w[i];
    					maxValue += v[i];
    				}else { 
    					maxValue += weight*price[i];
    					weight = 0;
    				}
    				//System.out.println(weight+"-->"+maxValue);
    			}else { 
    				break;
    			}
    		}
    		System.out.println(maxValue);
    	}
    
    	private static void sort(double[] w, double[] v, double[] price) { 
    		for(int i = 0; i < price.length - 1; i++) { 
    			for(int j = i + 1; j < price.length; j++) { 
    				if(price[i] < price[j]) { 
    					swap(w, v, price, i, j);
    				}
    			}
    		}
    		System.out.print("重量：");
    		for(double i : w) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    		
    		System.out.print("价格：");
    		for(double i : v) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    		
    		System.out.print("单价：");
    		for(double i : price) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    	}
    
    	private static void swap(double[] w, double[] v, double[] price, int i, int j) { 
    		double temp;
    		temp = w[i];
    		w[i] = w[j];
    		w[j] = temp;
    		
    		temp = v[i];
    		v[i] = v[j];
    		v[j] = temp;
    		
    		temp = price[i];
    		price[i] = price[j];
    		price[j] = temp;
    	}
    }

# 钢条切割 #

/* * Serling公司购买长钢条，将其切割为短钢条出售，切割工序本身没有成本支出，公司管理层希望知道最佳的切割方案 * 假定知道公司出售一段长为i英寸的钢条的价格为pi(i=1,2,...,单位为美元) * 长度： 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 * 价格： 1 | 5 | 8 | 16 | 10 | 17 | 17 | 20 | 24 | 30 * 钢条切割问题：给定一段长度为n英寸的钢条和一个价格表pi，求切割钢条方案，使得销售收益rn最大 */
    public class _钢条切割 { 
    	
    	static int n = 10;
    	static int[] p = { 1, 5, 8, 16, 10, 17, 17, 20, 24, 30};
    	static int[] vs = new int[n+1];
    	//记忆型递归
    	static int r(int x) { 
    		if(x == 0)
    			return 0;
    		int ans = 0;
    		for(int i = 1; i <= x; i++) { 
    			if(vs[x - i] == -1)
    				vs[x - i] = r(x - i);
    			int v = p[i - 1] + vs[x - i];
    			ans = Math.max(v, ans);
    		}
    		vs[x] = ans;
    		return ans;
    	}
    	//dp解法
    	static int dp(int x) { 
    		vs[0] = 0;
    		for(int i = 1; i <= x; i++) {  //拥有的钢条的长度
    			for(int j = 1; j <= i; j++) { //可切割的钢条长度
    				vs[i] = Math.max((p[j - 1] + vs[i - j]), vs[i]);
    			}
    		}
    		return vs[n];
    	}
    	public static void main(String[] args) { 
    		Arrays.fill(vs, -1);
    		int ans = r(n);
    		System.out.println(ans);
    		
    		Arrays.fill(vs, -1);
    		ans = dp(n);
    		System.out.println(ans);
    	}
    }

# 区间调度 #

/* * 贪心问题 * 区间调度（不相交区间） * 有n项工作，每项工作分别在s时间开始，t时间结束 * 对于每项工作，你都可以选择参加或不参加，如果选择了参与，那么自始至终都要参加 * 此外，参与工作的时间段不能重复（即后一项工作的时间和前一项工作的时间不能重叠） * 那么最多能参与多少项工作？ * * 输入： * 第一行:n * 第二行:n个整数空格隔开，代表n个工作的开始时间 * 第三行:n个整数空格隔开，代表n个工作的结束时间 * * 样例 * 输入： * 5 * 1 2 4 6 8 * 3 5 7 9 10 * * 输出： * 3 */
    public class _区间调度 { 
    	static int n;//有n项工作
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		int[] s = new int[n]; //开始时间数组
    		int[] t = new int[n];//结束时间数组
    		for(int i = 0; i < n; i++) { 
    			s[i] = sc.nextInt();
    		}
    		for(int i = 0; i < n; i++) { 
    			t[i] = sc.nextInt();
    		}
    		sort(s, t);//将结束时间从小到大排序，对应的开始时间也要变换顺序
    		int res = f(n, s, t);
    		System.out.println(res); 
    	}
    	
    	private static void sort(int[] s, int[] t) { 
    		for(int i = 0; i < t.length - 1; i++) { 
    			for(int j = i + 1; j < t.length; j++) { 
    				if(t[i] > t[j]) { 
    					int temp = t[i];
    					swap(s, t, i, j);
    				}
    			}
    		}
    		for(int i : s) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    		for(int i : t) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    	}
    
    	private static void swap(int[] s, int[] t, int i, int j) { 
    		int temp;
    		temp = t[i];
    		t[i] = t[j];
    		t[j] = temp;
    		
    		temp = s[i];
    		s[i] = s[j];
    		s[j] = temp;
    	}
    
    	public static int f(int n, int[] s, int[] t) { 
    		int cnt = 1;
    		int y = t[0];//结束时间最早的工作
    		for(int i = 1; i < n; i++) { 
    			if(s[i] > y) {  //如果下一项工作的开始时间比上一项工作的结束时间晚
    				cnt++;
    				y = t[i];
    			}
    		}
    		return cnt;
    	}
    }

# 区间覆盖 #

/* * 在给定的N个区间中，求解覆盖某个区间的最少区间数 * 样例输入： * 3 10（3表示需要输入3个区间，10表示1-10这个区间） * 1 7 * 3 6 * 6 10 * 输出： * 2 */
    public class _区间覆盖 { 
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int T = sc.nextInt();
    		int[] s = new int[N];
    		int[] t = new int[N];
    		for(int i = 0; i < N; i++) { 
    			s[i] = sc.nextInt();
    			t[i] = sc.nextInt();
    		}
    		sort(s, t);
    		int start = 1;
    		int end = 1;
    		int ans = 0;
    		for(int i = 0; i < N; i++) { 
    			int ss = s[i];
    			int tt = t[i];
    			if(i == 0 && ss > 1)//不符合
    				break;
    			if(ss <= start) { 
    				end = Math.max(tt, end);
    			}else { 
    				ans++;
    				start = end + 1;
    				if(ss <= start) { 
    					end = Math.max(tt, end);
    				}else { 
    					break;
    				}
    			}
    		}
    		if(end < T)
    			System.out.println(-1);
    		else
    			System.out.println(++ans);
    	}
    
    	private static void sort(int[] s, int[] t) { 
    		for(int i = 0; i < t.length - 1; i++) { 
    			for(int j = i + 1; j < t.length; j++) { 
    				if(s[i] > s[j]) { 
    					int temp = s[i];
    					swap(s, t, i, j);
    				}
    			}
    		}
    		for(int i : s) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    		for(int i : t) { 
    			System.out.print(i+" ");
    		}
    		System.out.println();
    	}
    	private static void swap(int[] s, int[] t, int i, int j) { 
    		int temp;
    		temp = t[i];
    		t[i] = t[j];
    		t[j] = temp;
    		
    		temp = s[i];
    		s[i] = s[j];
    		s[j] = temp;
    	}
    }

# 数字三角形 #

/* * 在数字三角形中国寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大 * 路径上的每一步都只能往左下或右下走，只需要求出这个最大和即可，不必给出具体路径 * 输入格式： * 5 （表示行数） * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 * 思路：确定下一行的最大值，从下往上递推 */
    public class _数字三角形 { 
    	static int N;
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		int[][] triangle = new int[N][N];
    		for(int i = 0; i < N; i++) { 
    			for(int j = 0; j <= i; j++) { 
    				triangle[i][j] = sc.nextInt();
    			}
    		}
    		int ans = f1(triangle);
    		System.out.println(ans);
    	}
    
    	private static int f1(int[][] triangle) { 
    		for(int i = N-1; i >= 0; i--) { 
    			for(int j = 0; j <= i; j++) { 
    				if(i == N - 1) {  }
    				else { 
    					triangle[i][j] = triangle[i][j]+Math.max(triangle[i+1][j], triangle[i+1][j+1]);
    				}
    			}
    		}
    		return triangle[0][0];
    	}
    }

# 硬币支付 #

/*贪心问题一 * 有1元，5元，10元，50元，100元，500元的硬币各有C1,C5,C10,C50,C100,C500枚 * 现在要用这些硬币来支付A元，最少需要多少枚硬币？ * * 输入第一行6个数字分别代表每种面值，第二行是需要支付的总金额 * 例如输入 * 3 2 1 3 0 2 * 620 * 输出 * 6 * (6=1(*500)+2(*50)+1(*10)+2(*5)) */
    public class _硬币支付 { 
    	static int[] cnts = new int[6];
    	static int[] coins = { 1,5,10,50,100,500};
    	static int A;
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		
    		for(int i = 0; i < 6; i++) { 
    			cnts[i] = sc.nextInt();
    		}
    		A = sc.nextInt();
    		int res = f(A, 5);
    		System.out.println(res);
    	}
    	private static int f(int A, int cur) { 
    		if(A <= 0)
    			return 0;
    		if(cur == 0)
    			return A;
    		int coinValue = coins[cur];
    		int x = A/coinValue;
    		int cnt = cnts[cur];
    		int t = Math.min(x, cnt);
    		
    		return t+f(A-t*coinValue, cur-1);
    	}
    }

# 字典序最小 #

public class _字典序最小 { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		StringBuilder sb = new StringBuilder();
    		sb.append(sc.nextLine());
    		
    		f(sb.toString());
    	}
    
    	public static void f(String str) { 
    		//将原来的字符串翻转，为了方便比较首尾字典序
    		String reverse_str = new StringBuilder(str).reverse().toString();
    		int len = str.length();
    		StringBuilder new_str = new StringBuilder();
    		int cnt = 0;
    		while(new_str.length() < len) { 
    			if(str.compareTo(reverse_str) <= 0) { 
    				new_str.append(str.charAt(0));
    				str = str.substring(1);
    			}else { 
    				new_str.append(reverse_str.charAt(0));
    				reverse_str = reverse_str.substring(1);
    			}
    			
    		}
    		print(new_str.toString());
    	}
    	
    	public static void print(String new_str) { 
    		int len = new_str.length();
    		int cnt = len/80;
    		if(cnt <= 1)
    			System.out.println(new_str);
    		else { 
    			int i;
    			for(i = 0; i < cnt; i++) { 
    				System.out.println(new_str.substring(i*80, (i+1)*80)); 
    			}
    			if(len%80!=0)
    				System.out.println(new_str.substring(i*80));   
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/0c2fbe3891a545798dd63deba66a58eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201027183202175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ==,size_16,color_FFFFFF,t_70#pic_center
[20201027212303854.png_pic_center]: /images/20221122/958e98f44ec14d1ba8a30f3399035eb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/7b49c2bb73204ea5b4592e6e92bf37da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221122/ad4dd990ad3f4605b1feb0cc267758eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221122/64cd82d4da7b486180659d9eb2017269.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221122/96a5a05fdfb04416b0765e01f2f4f203.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221122/c6d4be49e9284f78a433e7a31766fc27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hvc2hpem9sYQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221122/0e0912b8157f4a0dabeb09d83d0f09d0.png