这是一个编码问题。但是，我不需要代码中的答案。我只是需要帮助来弄清楚这个问题背后的数学。 [英] This is a coding question. However, I do not require the answer in code. I just need help in figuring out the math behind this question.

问题描述

你是一名职业强盗，计划在街上抢劫房屋。每个房子都有一定数量的钱存在，阻止你抢劫他们的唯一限制是相邻的房屋连接了安全系统，如果两个相邻的房屋在同一个晚上被闯入，它将自动联系警察。



给出一个代表每个房子的金额的非负整数列表，确定今晚可以抢劫的最高金额，而不会警告警察。



注意：列表实际上是一个整数数组，其中元素索引表示房屋的位置，元素是存储在其中的金额。强盗无法抢夺相邻指数。作为样本，阵列如下



[10 50 7 15 500 100]



< b>我尝试了什么：



我想到的只是添加备用元素，但这种逻辑在许多情况下都不会给出正确的结果，特别是对于样本我已经把我的问题包括在内了。在这种情况下正确的答案只是添加500和50.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

NOTE: The "list" is actually an array of integers where the index of element means the position of the house and the element is the amount of money stashed in it. Robber cant rob adjacent indices. As a sample, the array is as follows

[10 50 7 15 500 100]

What I have tried:

I thought of just adding up alternate elements but this logic wont give correct result for many cases, especially for the sample I have included in my question. The right answer in this case is just adding 500 and 50.

推荐答案

原则：您需要找到符合不报警标准的房屋组合。对于每种组合，计算金额。保持最佳状态。



拿一张纸，每个房子使用一列，每个组合一排。

看你如何绘制第一个组合，看看你如何到达下一个，以及你如何知道你到底。

你的程序将遵循相同的原则。



作为程序员，你的工作是创建算法解决特定问题，你不能依赖别人为你永远做到这一点，所以有一段时间你需要学习如何。越快越好。

创建算法基本上是找到数学并进行必要的调整以适应您的实际问题。



[更新]

The principle: you need to find every combination of house that meet the criteria of not calling the police. For each combination, calc the amount of money. Keep the best.

Take a sheet of paper, use a column per house and a row per combination.
see how you draw the first combination, see how you get to the next one, and how you know you are at the end.
Your program will follow the same principle.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

[Update]

引用：

我实际上是在学习算法的过程中

I am actually in the process of learning algorithms

- 学习一种或多种分析方法， EW Djikstra自上而下的方法是一个良好的开端。

https：// en.wikipedia.org/wiki/Top-down_and_bottom-up_design [ ^ ]

https://en.wikipedia.org/wiki/Structured_programming [ ^ ]

https://en.wikipedia.org/wiki/Edsger_W._Dijkstra [ ^ ]

https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF [ ^ ]



有趣的链接：

学习编程 [ ^ ]

- Learn one or more analyze methods, E.W. Djikstra top-Down method is a good start.
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
https://en.wikipedia.org/wiki/Structured_programming[^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]

Interesting link:
Learn to Program[^]

引用：

我想只是添加备用元素

为什么？

你应该尝试添加所有'不相邻的项目'（'替代项目'是一个子集）。

这并不困难，两个嵌套循环就足够了。

Why?
You should try to add all 'not-adjacent items' ('alternate items' is a subset).
It is not difficult, two nested loops would be enough.

这篇关于这是一个编码问题。但是，我不需要代码中的答案。我只是需要帮助来弄清楚这个问题背后的数学。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！