动态规划经典题目之一(斐波那契数列变形)

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

22

1.问题描述

        给定一个只含正数的数组,找到数组满足条件的元素的最大和,条件是:组成最大和的所有元素不能相邻,比如数组 [3,2,7,10] 返回 13(3+10),数组 [3,2,5,10,7] 返回(3+5+7)

2.问题分析

        

i01234
arr[i]325107

 

首先我们定义Optimal[i]为取第i个数时所能获得的最大效益,也就是从前往后取时,取到第i个所能得到的,满足条件的元素的最大和。

那么对 i = 4,arr[i] = 7,进行分析

当取到第4个数时,能获得的最大效益Optimal[4] 分为两种情况

        1. 取第4个数            

        2. 不取第4个数

是否取第4个数,我要看哪种情况我能获得最大效益,

        1. 取第四个数那么意味着我要放弃第三个数的最大效益,也就是说arr[4] + Optimal[2] > Optimal[3]

                   Optimal[4] = arr[4] + Optimal[2]

        2.不取第四个数那么意味着我选择了第三个数的最大效益,也就是说arr[4] + Optimal[2] < Optimal[3]

                   Optimal[4] = Optimal[3]

3.最优子结构

经过上面的分析我们可以得到,

Optimal[i] = max(取第i个数,不取第i个数);

                  = max(Optimal[i - 2] + arr[i] , Optimal[i - 1]);

初始条件

       当i=0时,能获得的最大效益只有 arr[0] ,所以Optimal[0] = arr[0];

       当i=1时, 则Optimal[1] = max(arr[0],arr[1]) ,只有两个数,我只能取一个

4.代码    

#include 
using namespace std;
int dp_opt(int* data,int data_length)
{int* opt = new int[data_length + 1];memset(opt,0,sizeof(int)*(data_length + 1));opt[0] = data[0];opt[1] = data[0] > data[1] ? data[0] : data[1];for(int i = 2;i < data_length;i++){int d1 = data[i] + opt[i - 2];int d2 = opt[i - 1];if(d1 > d2) opt[i] = d1;else opt[i] = d2;}return opt[data_length - 1];
}
int main()
{int* data;int data_length;cin >> data_length;data = new int[data_length + 1];for(int i = 0;i < data_length;i++){data[i] = rand() %10;cout << data[i] << " ";}cout << endl;cout << dp_opt(data,data_length) << endl;
}