动态规划选讲2

简介

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

动态规划选讲1

LeetCode 1027 最长等差数列

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

示例 1：

示例 2：

示例 3：

提示：

1. 2 <= A.length <= 2000
2. 0 <= A[i] <= 10000

分析：

构造一个dp的map类型数组，其中dp[d][x]代表在第x位之前，公差为d的等差数列的长度。显然初始化答案为2，先来一个正常循环，接下来在当前数字i之前的所有数组进行判断，先求出公差d，然后公差d的dp数组是否包含数字j，如果包含则dp[d][i] = dp[d][j] + 1，否则设置为2。

C++代码：

LeetCode 873 最长的斐波那契子序列的长度

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

示例 2：

提示：

• 3 <= A.length <= 1000
• 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
• （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

分析：

dp数组dp[i][j]代表从i到j斐波那契数组的长度，如果存在tmp = A[i] + A[j]，则有dp[i][j] = dp[j][M[tmp]] + 1;

C++代码：