动态规划详解 —— 蓝桥杯 摆动序列

1.摆动序列

• 题目描述：
  如果一个序列满足下面的性质，我们就将它称为摆动序列：
  　　1. 序列中的所有数都是不大于k的正整数；
  　　2. 序列中至少有两个数。
  　　3. 序列中的数两两不相等；
  　　4. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。
  　　比如，当k = 3时，有下面几个这样的序列：
  　　1 2
  　　1 3
  　　2 1
  　　2 1 3
  　　2 3
  　　2 3 1
  　　3 1
  　　3 2
  　　一共有8种，给定k，请求出满足上面要求的序列的个数。
• 输入格式：
  　　输入包含了一个整数k。（k<=20）
• 输入格式：
  　　输出一个整数，表示满足要求的序列个数。

2.动态规划解题思路：

整体概况：题目所给的前三个条件均易理解，第四个条件可以简化为如果有三个数为：小、中、大，则满足条件的序列为1.中、小、大 2.中、大、小可以看出无论如何变化 中 数位序列的最左边，当扩充到长度为n的序列时，只要任意三个数满足以上条件，此序列就为符合条件的摆动序列；

1.子问题确定：最长上升子序列告诉我们元素最大值在子问题的使用表达中不可忽视，本题目就是以满足条件序列最大值以及序列长度作为子问题进行解决的；

2.状态：状态数组dp[i][j]表示的含义为：i为所满足条件的序列中的最大值，j为序列长度（i 可以不包含在序列中，如i为4、j为3时，231、241均满足条件）；

3.初始状态：当序列长度为2时，即dp[i][2]时，没有所谓的中位数，只有大、小两个数，题目就转换为求排列组合的问题了，即：在i个数中选取2个数进行排列；

4.状态转移方程：
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
解释：
1.由2.状态解释可知，当长度为 j ，最大值为 i 时，其一定包含长度为 i，最大值为 i-1 的序列，因为由 i-1 到 i 其最大值变大了，所以一定包含；即：dp[i][j]=dp[i-1][j]+一个数
2.由整体概况解释可知，如果要满足题目序列，则任意三个数其中间大小的数应该为最左边；在推导过程中可知，当再增加一个较大的数值时应该舍弃原满足条件中的小，将这个新数添加到新的三个序列中去；
  dp表中的i行j列其实就相当于在i-1行j-1列中插入一个i，以i=3，j=3举例：它就相当于在 12 和 21序列里面插入3这个数字，插入后要满足题目第四点给出的情况，我们只能是在 21 里面插，因为在 12 里面插无论如何也不能满足中间的数在最左边而对于 21 来说只能插在最右边和中间，因为i是最大的数字，i不能在左边。所以有两种插入情况。
推广到更大的长度来说，有一半的排列是不能插的，而对于另一半来说，这个最大的数可以插在最右边和倒数第二个位置。如果再往左边的话，就会不满足题目要求了。所以相当于(i-1)(j-1)的情况除2再乘2等于本身。所以，加的另一个数位dp[i-1][j-1]：再长度为 j-1 的序列中，插入更大的数 i

3.AC代码：

import java.util.*;

public class Main {
	/*如果三个数为：小、中、大，则满足条件的为两种：1.中、大、小	2.中、小、大————即：中在最左边
	 * */
	
	public static int[][] dp;	//状态数组，
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		dp=new int[k+1][k+1];
		
		for(int i=2;i<=k;i++) {	//初始化状态数组
			dp[i][2]=i*(i-1);
		}
		
		for(int i=3;i<=k;i++) {
			for(int j=3;j<=k;j++) {
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];	//状态转移方程
			}
		}
		
		int cnt=0;	//计数
		for(int i=2;i<=k;i++) {
			cnt+=dp[k][i];		//计算最大值为k，长度由2到k所有满足条件的序列
		}
		System.out.println(cnt);
	}
}

本文地址：https://blog.csdn.net/weixin_43715360/article/details/107480924