Tag - "动态规划"
2022
题目描述
链接: https://leetcode-cn.com/problems/maximum-product-subarray/
给你一个整数数组nums, 请你找出数组中成绩最大的非空连续子数组(该子数组中至少包含一个数字), 并返回该子数组所对应的乘积.
示例1:
输入: [2, 3, -2, 4]
输出: 6
子数组 [2, 3]得到最大乘积6
输入 [-2, 0 -,1]
输出: 0
题目描述
链接: https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/
给定一个整数数组nums, 求乘积为正数的最长子数组的长度
示例1:
输入: [1, -2, -3, 4]
输出: 4
数组本身乘积就是正数
示例2:
输入: [0, 1, -2, -3, -4]
输出: 3
最长乘积为整数的子数组为[1, -2, -3]
题目描述
链接: https://leetcode-cn.com/problems/maximum-subarray/
给你一个整数数组nums, 请你找出一个具有最大和的连续子数组(子数组最少包含一个元素), 返回其最大和
子数组是数组中的一个连续部分
示例1:
输入: nums =[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出: 6
连续子数组 [4, -1, 2, 1]的和最大, 为6.
示例2:
输入: nums = [1]
输出: 1
示例3:
输入: nums = [5, 4, -1, 7, 8]
输出: 23
题目描述
链接: https://leetcode-cn.com/problems/min-cost-climbing-stairs/
给定一个整数数组cost, 其中cost[i]表示从楼梯第i个台阶向上爬需要支付的费用. 每次只能向上爬一个或两个台阶.
可以从下标0或下标1的台阶开始爬楼梯.
求到达楼梯顶部的最低花费
示例1:
输入 cost = [10, 15, 20]
输出: 15
从下标1开始爬, 向上2格. 到达楼梯顶部.
示例2:
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6
题目描述
链接: https://leetcode-cn.com/problems/delete-and-earn/
给你一个整数数组nums, 可以对他进行一些操作. 每次操作中, 选择任意一个nums[i], 删除它然后获取nums[i]的点数. 同时还需要删除所有 等于nums[i]-1和nums[i]+1的元素. 例如删除3, 那么得到3个点数, 同时需要在数组中删除所有的2和4.
开始时拥有0个点数, 求你能通过这些操作获取的最大点数.
示例1:
输入: nums = [3, 4, 2]
输出: 6
删除4和2.得到6点.
删除4获取4个点数, 同时3也被删除.
还剩下2, 然后删除2再得到2个点数.
示例2:
输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
删除3, 总共可以得到9个点数(3*3). 同时删除2和4.
最终得到9个点数.
题目描述
链接: https://leetcode-cn.com/problems/house-robber-ii/
你是一个专业的小偷, 计划偷窃沿街的房屋, 每间房内都藏有一定的现金. 这个地方所有的房屋都 围成一圈, 这意味着第一个房屋和最后一个房屋是紧挨着的. 同时, 相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入, 系统会自动报警 .
给定一个代表每个房屋存放金额的非负整数数组, 计算你在不触动警报装置的情况下,今晚能够偷窃到的最高金额.
示例1:
输入：nums = [2,3,2]
输出：3
你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例2:
输入：nums = [1,2,3,1]
输出：4
你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）. 偷窃到的最高金额 = 1 + 3 = 4 .
题目描述
链接: https://leetcode-cn.com/problems/house-robber/
你是一个专业的小偷, 计划偷窃沿街的房屋, 每间房内都藏有一定的现金, 影响你偷窃的唯一限制因素是相邻的房屋装有相互连通的防盗系统. 如果两间相邻的房屋在同一晚上被小偷闯入, 系统会自动报警.
给定一个代表每个访问存放金额的非负整数数组, 计算你在不触发警报装置的情况下, 一夜之内能够偷窃到的最高金额.
示例1:
输入: [1, 2, 3, 1]
输出: 4
偷窃1号和3号. 得到1+3 = 4.
示例2:
输入: [2, 7, 9, 3, 1]
输出: 12
偷窃1号, 3号和5号. 得到2+9+1 = 12.
2019
题目描述
链接: https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。问你有多少种不同的方法可以爬到楼顶？
示例 1：
输入： 2 输出： 2 有两种方法可以爬到楼顶。
第一种: 1 阶 + 1 阶
第二种: 2 阶
示例 2：
输入： 3
输出： 3
有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶