Next Topic

线性动态规划-不相邻数的最大和

数据结构与算法第十章动态规划线性动态规划-不相邻数的最大和

洛谷：P7482

已知数列V有n个数据，从中选择若干不相邻的数据，使其和值最大，选择数据的限制条件：若选择了V[i]，就不能选V[i+1]。

arr[] = [5, 5, 10, 100, 10, 5] output:110
arr[] = [3, 2, 7, 10] output:13
arr[] = [9, 1, 6, 10] output:19

动态规划分析

1. 状态定义

用 dp[i] 表示以第 i 个元素为结尾，能够获得的最大和。
转移关系涉及两个选择：
1. 不选当前元素 V[i]，那么最大和为 dp[i−1]。
2. 选当前元素 V[i]，那么前一个元素不能选，最大和为 dp[i−2]+V[i]。

2. 状态转移方程

dp[i]=max⁡(dp[i−1],dp[i−2]+V[i])

dp[i−1]：表示不选第 i个元素时的最大和。
dp[i−2]+V[i]：表示选第 i个元素时的最大和。

3. 边界条件

dp[0]=max⁡(0,V[0])：只有一个元素时，最大和为其本身或者 0（如果全是负数，结果为 0）。
dp[1]=max⁡(dp[0],V[1])：前两个元素的最大和。

4. 最终解

问题的解是 dp[n−1]，表示以数组最后一个元素为结尾的最大和。

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-31 14:02:14
 * 最后修改: 2024-12-31 14:14:03
 * 文件描述: 求解不相邻数的最大和
****************************************************************/

#include <iostream>
#include <vector>
using namespace std;

// 求解不相邻数的最大和
int maxNonAdjacentSum(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0; // 空数组
    if (n == 1) return max(0, nums[0]); // 只有一个数

    vector<int> dp(n, 0); // dp[i] 表示以第 i 个元素为结尾的最大和

    // 边界条件
    dp[0] = max(0, nums[0]);
    dp[1] = max(dp[0], nums[1]);

    // 动态规划递推
    for (int i = 2; i < n; ++i) {
        // 对于当前元素nums[i]，有两种选择：
        // 1. 不选当前元素，那么最大和就是dp[i - 1]
        // 2. 选当前元素，那么最大和就是dp[i - 2] + nums[i]（因为不能选相邻的i-1元素）
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[n - 1]; // 返回最后一个状态的最大值
}

int main() {
    int n;
    cout << "请输入数组长度：";
    cin >> n;
    vector<int> nums(n);

    cout << "请输入数组元素：";
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = maxNonAdjacentSum(nums);
    cout << "不相邻数的最大和为：" << result << endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Topic