[HOT 100]今日一练------打家劫舍

张开发
• 2026/4/21 12:20:28 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

[HOT 100]今日一练------打家劫舍
题目链接https://leetcode.cn/problems/house-robber/?envTypestudy-plan-v2envIdtop-100-liked思路动态规划动态转移方程主要取决于两种情况偷这家不偷上家不偷这家偷或者不偷上家由上述两种情况我们便可以得到我们的动态转移方程在此之前我们先引入所需变量以便表示方程f[i]表示选择偷这家时能拿到的最大的钱g[i]表示选择不偷这家时能拿到的最大的钱因此我们可以将动态转移方程表示为f[i] g[i-1] nums[i]g[i] Math.max(f[i-1], g[i-1])不过需要注意的时在正式进行动态规划之前我们要先进行初始化f[0] nums[0]g[0] 0动态规划完成之后的结果会剩下最后一家而对于最后一家来说我们有两种选择偷或者不偷因此我们只需要判断这两种方案哪个我们可以拿到最多的钱即Math.max(f[n-1]. g[n-1])代码class Solution { //动态规划 public int rob(int[] nums) { int n nums.length; if(n 0) return 0; //选择该数时和的最大值 int[] f new int[n]; //不选择该数时和的最大值 int[] g new int[n]; //初始化 f[0] nums[0]; g[0] 0; for(int i 1; i n; i) { f[i] g[i-1] nums[i]; g[i] Math.max(f[i-1], g[i-1]); } return Math.max(f[n-1], g[n-1]); } }

更多文章