利用C语言求解信息熵,动态规划选讲2

利用C语言求解信息熵,动态规划选讲2

简介

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

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：

输入：[3,6,9,12]

输出：4

解释：

整个数组是公差为 3 的等差数列。

1

2

3

4

输入：[3,6,9,12]

输出：4

解释：

整个数组是公差为3的等差数列。

示例 2：

输入：[9,4,7,2,10]

输出：3

解释：

最长的等差子序列是 [4,7,10]。

1

2

3

4

输入：[9,4,7,2,10]

输出：3

解释：

最长的等差子序列是[4,7,10]。

示例 3：

输入：[20,1,15,3,10,5,8]

输出：4

解释：

最长的等差子序列是 [20,15,10,5]。

1

2

3

4

输入：[20,1,15,3,10,5,8]

输出：4

解释：

最长的等差子序列是[20,15,10,5]。

提示：

2 <= A.length <= 2000

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++代码：

C++

class Solution {

public:

int longestArithSeqLength(vector& A) {

map > dp; //dp[i][j]代表在第j位之前，公差d的等差数列长度

int ans = 2;

for(int i = 1; i < A.size(); i++){

for(int j = 0; j < i; j++){

int d = A[i] - A[j];

if(dp[d].count(j) > 0)dp[d][i] = dp[d][j] + 1; //如果存在i之前相同的d，则加1

else dp[d][i] = 2;

ans = max(ans, dp[d][i]);

}

}

return ans;

}

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

classSolution{

public:

intlongestArithSeqLength(vector&A){

map>dp;//dp[i][j]代表在第j位之前，公差d的等差数列长度

intans=2;

for(inti=1;i

for(intj=0;j

intd=A[i]-A[j];

if(dp[d].count(j)>0)dp[d][i]=dp[d][j]+1;//如果存在i之前相同的d，则加1

elsedp[d][i]=2;

ans=max(ans,dp[d][i]);

}

}

returnans;

}

};

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：

输入: [1,2,3,4,5,6,7,8]

输出: 5

解释:

最长的斐波那契式子序列为：[1,2,3,5,8] 。

1

2

3

4

输入:[1,2,3,4,5,6,7,8]

输出:5

解释:

最长的斐波那契式子序列为：[1,2,3,5,8]。

示例 2：

输入: [1,3,7,11,12,14,18]

输出: 3

解释:

最长的斐波那契式子序列有：

[1,11,12]，[3,11,14] 以及 [7,11,18] 。

1

2

3

4

5

输入:[1,3,7,11,12,14,18]

输出:3

解释:

最长的斐波那契式子序列有：

[1,11,12]，[3,11,14]以及[7,11,18]。

提示：

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++代码：

C++

class Solution {

public:

int lenLongestFibSubseq(vector& A) {

vector>dp(A.size(), vector(A.size(), 0));

map M;

for (int i = 0; i < A.size(); i++)M[A[i]] = i;

int ans = 0;

for (int i = A.size() - 1; i >= 0; i--) {

for (int j = i + 1; j < A.size(); j++) {

dp[i][j] = 2;//默认为2

int tmp = A[i] + A[j];

if (M.count(tmp)) {

dp[i][j] = dp[j][M[tmp]] + 1;

if (dp[i][j] > ans) ans = dp[i][j];

}

}

}

return ans;

}

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

classSolution{

public:

intlenLongestFibSubseq(vector&A){

vector>dp(A.size(),vector(A.size(),0));

mapM;

for(inti=0;i

intans=0;

for(inti=A.size()-1;i>=0;i--){

for(intj=i+1;j

dp[i][j]=2;//默认为2

inttmp=A[i]+A[j];

unt(tmp)){

dp[i][j]=dp[j][M[tmp]]+1;

if(dp[i][j]>ans)ans=dp[i][j];

}

}

}

returnans;

}

};