动态规划选讲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++代码:

 

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注