如何用php和js代码动态规划实现“打家劫舍”的问题?
一名精通盗窃的贼意图侵入一排住家,每家中都有一定数量的现金。他遇到的问题是每对邻近的住宅都配备了联动的安全系统,一旦同一夜有两户人家遭到入侵,警报便会触发。
假设有一组非负整数的数组 nums=[2,3,2,4],数字内数字代表每户的现金数量,目标是在不激活安全系统的前提下,计算这位贼单夜内能够盗取的最大金额。
网友回复
php实现
<?php function rob(array $nums) { $n = count($nums); if ($n === 0) return 0; if ($n === 1) return $nums[0]; $dp = [$nums[0], max($nums[0], $nums[1])]; for ($i = 2; $i < $n; $i++) { $dp[$i % 2] = max($dp[($i - 1) % 2], $nums[$i] + $dp[($i - 2) % 2]); } return $dp[($n - 1) % 2]; } // 测试数组 $nums = [2, 7, 9, 3, 1]; echo rob($nums); // 输出应为 12 ?>
js实现
function rob(nums) { const n = nums.length; if (n === 0) return 0; if (n === 1) return nums[0]; let dp = [nums[0], Math.max(nums[0], nums[1])]; for (let i = 2; i < n; i++) { dp[i % 2] = Math.max(dp[(i - 1) % 2], nums[i] + dp[(i - 2) % 2]); } return dp[(n - 1) % 2]; } // 测试数组 console.log(rob([2, 7, 9, 3, 1])); // 输出应为 12