（2020复旦机试）序列

关键字：动态规划最大递增子序列变形问题

要找到关键的最优子问题：

• 把问题规模是i=0,i=1考虑清楚，依次的计算出来即可
• dp[i][j] 即第i个位置为j时能达到的最小距离值，也有点像背包问题，有点像最大公共子序列问题

代码：

#include<vector>
#include<algorithm>
using namespace std;
/*
6
1 4 2 8 5 7
*/
int main() {
	int n;
	cin >> n;
	vector<int> numsA(n), numsB(n);
	for (int i = 0; i < n; i++) {
		cin >> numsA[i];
	}
	vector<vector<int>> dp(n, vector<int>(10, 1e6));
	for (int i = 0; i <= 9; i++) {
		dp[0][i] = abs(i - numsA[0]);
	}
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= 9; k++) {
				int t = dp[i - 1][k] + abs(j - numsA[i]) + pow(j - k, 2);
				dp[i][j] = min(t, dp[i][j]);
			}
			//cout << "dp[ " << i << " , " << j << " ] = " << dp[i][j] << endl;
		}
	}
	int res = 1e6;
	for (int i = 0; i < n; i++) {
		res = min(res, dp[n - 1][i]);
	}
	cout << res << endl;
}