2022.02.12 - SX10-29.打家劫舍

news/2024/10/30 9:34:37/

文章目录

  • 1. 题目
  • 2. 思路
    • (1) 动态规划
  • 3. 代码

1. 题目

在这里插入图片描述

2. 思路

(1) 动态规划

  • dp[i]表示打劫前i个房屋获得的最高金额。
  • 对于第i个房屋,有两种选择,若实施打劫,则获得的金额为dp[i-2]+nums[i];若不实施打劫,则获得的金额为dp[i-1]。因此,dp[i]取两者较大的一个即可。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int rob(int[] nums) {int n = nums.length;if (n == 1) {return nums[0];}int[] dp = new int[n];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[n - 1];}
}

http://www.ppmy.cn/news/155043.html

相关文章

2022.02.17 - SX10-39.买卖股票的最好时机含手续费

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 只需在计算dp[i][1]时&#xff0c;考虑前一天持有股票而这一天卖出的情况下&#xff0c;减去手续费即可。 3. 代码 public class Test {public static void main(String[] args) {} }class Solu…

2022.02.02 - SX10-24.完全平方数

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 dp[i]表示和为i的完全平方数的最少数量&#xff0c;则可以枚举[1,根号i]的所有数字&#xff0c;对于数字j来说&#xff0c;dp[i]dp[i-j*j]1。对于每一个数字i&#xff0c;都要遍历其所有的[1,根号…

2022.01.16 - SX10-16.目标和

文章目录 1. 题目2. 思路(1) 动态规划(2) 动态规划优化 3. 代码 1. 题目 2. 思路 (1) 动态规划 这道题可以转化为0/1背包问题&#xff0c;由于总和sum和目标和target已经确定&#xff0c;因此&#xff0c;要求的即是从数组中挑出和为(sum-target)/2的方案数。首先确定动态规划…

2022.01.18 - SX10-21.组合总和 Ⅳ

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 动态规划数组dp[i]表示总和为i的组合的个数&#xff0c;初始化时&#xff0c;dp[0]1。对于总和为i-num的每一种排列&#xff0c;在最后添加num后即可得到总和为i的排列&#xff0c;因此&#xff0…

2022.01.19 - SX10-22.爬楼梯

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 动态规划数组dp[i]表示爬到第i个台阶的方案数&#xff0c;累加最后一步的所有方案数即可。注意&#xff01;转化为完全背包问题即为容量在外&#xff0c;物品在内。 3. 代码 public class Test …

2022.02.13 - SX10-30.打家劫舍 II

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 由于第一家和最后一家只能选择一家偷&#xff0c;另一家必然不能偷&#xff0c;因此&#xff0c;可以直接删除第一家或者最后一家&#xff0c;这样就断开了环&#xff0c;分别进行动态规划&#x…

IV XXSC-11

文章目录 展示管理员列表CV代码说明通过管理员列表页面,删除管理员管理员权限实际操作步骤如下 事务 展示管理员列表 删除数据后可以选择本地删除,而无需重新请求服务器获取数据,这样可以不占用网络和服务器资源 但是也存在问题,就是别的用户在访问,你没及时删除,看到的是假的…

【回答问题】ChatGPT上线了!给我推荐20个比较流行的深度学习模型

目录 给我推荐20个比较流行的nlp模型给我推荐20个比较流行的计算机视觉模型给我推荐20个比较流行的图像分类模型给我推荐20个比较流行的人脸识别模型给我推荐20个比较流行的实体识别模型给我推荐20个比较流行的语言识别模型给我推荐20个比较流行的激光雷达3D点云模型给我推荐20…