题解 | 不相邻取数
不相邻取数
https://www.nowcoder.com/practice/a2be806a0e5747a088670f5dc62cfa1e
解题思路
这是一个求不相邻数字最大和的问题，可以通过动态规划来解决：
- 定义
表示前
个数中能选择的不相邻数字的最大和
- 对于第
- 选择第
- 不选择第
- 选择第
- 状态转移方程：
- 初始条件：
代码
#include <iostream>
#include <vector>
using namespace std;
long long maxSum(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector<long long> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << maxSum(nums) << endl;
return 0;
}
import java.util.*;
public class Main {
public static long maxSum(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
long[] dp = new long[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println(maxSum(nums));
}
}
def maxSum(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1]
n = int(input())
nums = list(map(int, input().split()))
print(maxSum(nums))
算法及复杂度
- 算法：动态规划
- 时间复杂度：
- 只需要遍历一次数组
- 空间复杂度：
的
数组
这道题本质上是打家劫舍问题的变体。关键在于理解每个位置都有"选"和"不选"两种状态：
- 如果选择当前数字，那么前一个数字一定不能选，此时的和为
- 如果不选当前数字，那么最大和就是前
个数字能得到的最大和
由于数据范围较大（），所以在实现时需要使用
long long（C++）或 long（Java）类型来避免整数溢出。
注意：虽然题目保证输入的数字不超过 ，但是和可能会很大，所以需要使用长整型。
