Anaconda env set

动态规划

最重要的是要找到状态转移方程，不然开过大的数组很有可能会内存溢出

区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题。

2019 年 9月 21 日

leetcode

不相邻数组取值问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

学习了leetcode的一些刷题方法，主要是动态规划的简单应用，学会用空间换时间的一些技巧

解决思路

设置两个变量，sumOdd 和 sumEven 分别对数组的奇数和偶数元素求和。
遍历数组，索引为奇数时，将元素加到奇数和，并与偶数和比较更新成max。
偶数和同理。
返回时进行最后一次更新max。
很值得借鉴

int sumOdd = 0;
	int sumEven = 0;

	for (int i = 0; i < nums.size(); i++)
	{
		if (i % 2 == 0)
		{
			sumEven += nums[i];
			sumEven = max(sumOdd, sumEven);
		}
		else
		{
			sumOdd += nums[i];
			sumOdd = max(sumOdd, sumEven);
		}
	}
	return max(sumOdd, sumEven);

官方的状态转移方程

f（k） = max（f(k-2)+A[k],f(k-1)）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 583614868@qq.com