We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
问题【LeetCode 198】: 一个小偷准备去偷一排别墅,但是相邻两个别墅被偷了会触发报警,所以在不出发报警的前提下,如何偷到最多的钱。 用数组表示一排别墅,比如 [1,2,5,2,1,3], index 为0的别墅和 index 为1的别墅相邻,index 为0的别墅可偷的钱为1。 如果是 [1,2,5,2,1,3],小偷偷到最多的钱总和为:1+5+3 = 9
The text was updated successfully, but these errors were encountered:
https://www.youtube.com/watch?v=-i2BFAU25Zk
分析:
对于每一栋别墅都有两种可能,偷,或者不偷,同时对应两个结果,偷后的总金额最大多少,不偷的总金额最大多少
假设偷和不偷对应的总净额分别为 r 和 nr:
第2栋房子: 偷:r = 1 不偷: nr = 0
第2栋房子: 偷:r = 2 不偷: nr = 1
.... 得到下表:
在比较 nr 和 r 的大小就可以得出,小偷可以偷到的最大金额为 9
转换成公式:
r[i] = nr[i-1] + currentNumber nr[i] = max(r[i-1], nr[i-1])
js代码:
cosnt robberNumber = (nums) => { if (!nums || nums.length === 0) return 0 let r = 0 let nr = 0 let temp = 0 for (let i = 0; i < nums.length; ++i) { temp = nr nr = Math.max(r, nr) r = temp + nums[i] } return Math.max(r, nr) } robberNumber([1,2,5,2,1,3]) // ==> 9
Sorry, something went wrong.
No branches or pull requests
问题【LeetCode 198】:
一个小偷准备去偷一排别墅,但是相邻两个别墅被偷了会触发报警,所以在不出发报警的前提下,如何偷到最多的钱。
用数组表示一排别墅,比如 [1,2,5,2,1,3], index 为0的别墅和 index 为1的别墅相邻,index 为0的别墅可偷的钱为1。
如果是 [1,2,5,2,1,3],小偷偷到最多的钱总和为:1+5+3 = 9
The text was updated successfully, but these errors were encountered: