动态规划

妖狐艹你老母 2022-05-11 04:56 280阅读 0赞

1.**题目：**最长递增子序列（Longest Increasing Subsequence）

**问题描述：**

> 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）。如给定数组A\{5，6，7，1，2，8\}，则A的LIS为\{5，6，7，8\}，长度为4.

**原理：**

> 因为子序列要求是递增的，所以重点是子序列的起始字符和结尾字符，因此我们可以利用结尾字符。
> 
> 分解问题：
> 
> 1. 初始化为1，即只输入一个数值；
> 
> 2.在当前位置（从第二个数值开始），如果当前数值大于之前任意的值，则当前的最大长度加1，小于则不操作；
> 
> 举例子
> 
> <table style="width:693px;"> 
> <tbody> 
> <tr> 
> <td>输入数值</td> 
> <td style="width:78px;">1</td> 
> <td style="width:84px;">3</td> 
> <td style="width:89px;">5</td> 
> <td style="width:102px;">7</td> 
> <td style="width:80px;">3</td> 
> <td style="width:93px;">4</td> 
> </tr> 
> <tr> 
> <td>对应位置的字符串长度a</td> 
> <td style="width:78px;">1</td> 
> <td style="width:84px;">2</td> 
> <td style="width:89px;">3</td> 
> <td style="width:102px;">4</td> 
> <td style="width:80px;">2</td> 
> <td style="width:93px;">3</td> 
> </tr> 
> <tr> 
> <td>备注（加的左值为之前长度最大值）</td> 
> <td style="width:78px;">初始肯定为1</td> 
> <td style="width:84px;">3&gt;1,故a=1+1</td> 
> <td style="width:89px;">5&gt;1且5&gt;3,故2+1</td> 
> <td style="width:102px;"> 7&gt;1 7&gt;2 7&gt;3 3+1 </td> 
> <td style="width:80px;"> 3&gt;1 3=3 3&lt;5 3&lt;7 故 1+1 </td> 
> <td style="width:93px;"> .. 4&gt;3 ... 4&gt;3 故 2+1 </td> 
> </tr> 
> </tbody> 
> </table>
> 
> 注意：主要对每个值得最大长度计算、之前端点最大值的判断，全局端点的最大值判断

#include<iostream>
 #include<algorithm>
 #include<vector>
 using namespace std;
 
 int maxlength(vector<int> numbers,int n) {
 	int result = 0;
 	vector<int> arr;	//初始化很重要
 	int temp = n;
 	while (temp--)
 		arr.push_back(0);
 
 	arr[0] = 1;		//动态规划初始条件，用于记录当前位置的最大字符串长度**
 	for (int i = 1; i < n; i++)		//表示当前端点开始，记录每个端点的最大字符串长度
 	{
 		int max = 0;	//最大字符串长度,每一轮都重新赋值***
 		for (int j = 0; j <i; j++)	//表示当前端点左边遍历，使其得到最大字符串紧邻的字符，并记录当前的长度
 		{
 			if ((numbers[i] > numbers[j]) && (arr[j] > max))//当前大于其之前端点且之前的端点的的最大长度大于原先的最大长度，则重新设置最大长度
 			{												//即，取得之前端点最大长度的大小，给max									
 				max = arr[j];
 			}
 		}
 		arr[i] = max + 1;		//当全部扫描完之前的端点，加1获得当前节点大小
 		if (arr[i] > result)	//获得所有最大的长度值
 			result = arr[i];
 	}
 	return result;
 }
 
 int main() {
 	int n;
 	while (cin >> n)
 	{
 		int a = 0;
 		vector<int> numbers;
 		for (int i = 0; i < n; i++) {
 			cin >> a;
 			numbers.push_back(a);
 		}
 		cout << maxlength(numbers, n) << endl;
 	}
 	system("pause");
 	return 0;
 }