当前位置:网站首页>【力扣刷题】一维动态规划记录(53零钱兑换、300最长递增子序列、53最大子数组和)
【力扣刷题】一维动态规划记录(53零钱兑换、300最长递增子序列、53最大子数组和)
2022-07-06 12:56:00 【李小恩恩子】
目录
一、322.零钱兑换
题目
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量是无限的。
解题思路
首先先明确dp数组的定义:输入一个目标金额n,返回凑出目标金额的最少硬币数量。
【base case】:amount = 0,返回0;
【状态】:唯一的目标金额;
【选择】:每选择了一枚硬币,就相当于减少了目标金额。
【状态转移方程】:
代码
自顶向下:带记忆的向下搜索,减少求解子问题的数量
class Solution {
public int coinChange(int[] coins, int amount) {
//一维
//记忆化搜索
//dp数组表示输入目标金额amount返回凑出目标金额最小的硬币数量
int[] dp = new int[amount + 1];
for(int i = 0;i <= amount;i++){
dp[i] = -99;//随便初始化一个特殊值,用来判断
}
return coin(coins,dp,amount);
}
public int coin(int[] coins,int[] dp,int amount){
if(amount == 0) return 0;
if(amount < 0) return -1;
//不重复计算,剪枝
if(dp[amount] != -99) return dp[amount];
int res = Integer.MAX_VALUE;
for(int coin = 0; coin < coins.length;coin++){
//子问题
int next = coin(coins,dp,amount-coins[coin]);
//子问题无解
if(next == -1) continue;
//在所有子问题中选出最优解,+1
res = Math.min(res,next + 1);
}
//记录结果,减少重复计算
dp[amount] = (res == Integer.MAX_VALUE) ? -1:res;
return dp[amount];
}
}
自底向上:dp数组的迭代求解
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
//amount+1相当于无穷大了,因为硬币数量最大也就是amount(全为1块的硬币的情况)
for(int i = 0;i < amount + 1 ; i++){
dp[i] = amount + 1;
}
dp[0] = 0;
for(int i = 0; i < amount + 1;i++){
//求所有子问题的最优解+1
for(int coin = 0; coin < coins.length; coin++){
if(i - coins[coin] < 0) continue;
dp[i] = Math.min(dp[i],dp[i - coins[coin]] + 1);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
}
二、300.最长递增子序列
题目
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解题思路
注意是要求子序列,不是子数组,子数组是连续的,子序列不是,可以不用连续。如上面示例1的子序列【2,3,7,101】。
dp数组的定义:dp[i]表示以nums[i]这个数结尾的最长递增子序列。
【base case】:dp[i]所有的值初始化为1,因为以nums[i]结尾的最长递增子序列最起码包括自己
【选择】:对于每一个dp[i],只需要找到前面所有比它小的元素的dp[j],再+1,找到其中的最大值即dp[i]。
【结果】:子序列的最大值,是dp数组中的最大值。
代码
class Solution {
public int lengthOfLIS(int[] nums) {
//动态规划
//定义dp[i]表示以元素nums[i]结尾的最长递增子序列
//对于每一个dp[i],只需要找到前面所有比它小的元素的dp[j],再+1,找到其中的最大值即dp[i]
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length;i++){
dp[i] = 1;//初始化,所有元素为1
}
int res = 1;
for(int i = 0; i < nums.length;i++){
for(int j = 0; j < i; j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
res = Math.max(res,dp[i]);
}
return res;
}
}
三、53.最大子数组和
题目
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组 是数组中的一个连续部分。
解题思路
和上面求【最长递增子序列】类似,定义dp数组含义:dp[i]表示以nums[i]结尾的最大子数组和。
【注意】:如果定义dp[i]数组为nums[0...i]中的最大子数组和,那么是求不出来的,因为推不出来dp[i+1],子数组必须是连续的,但不能保证dp[i]到dp[i+1]的时候:nums[0...i]中的最大子数组与nums[i+1]是相邻的。
【base case】:dp[0] = nums[0]
【选择】:判断大小做选择,①和前面相邻的元素连接组成更大子数组;②自己作为一个子数组
【结果】:子数组最大和,是dp数组中的最大值。
代码
class Solution {
public int maxSubArray(int[] nums) {
//动态规划
//定义dp[i]表示以nums[i]结尾的最大子数组和
//动态转移有两种选择,第一种和前面一个元素组合成更大的和,第二种自己一个人组
int[] dp = new int[nums.length];
dp[0] = nums[0];
for(int i = 1;i < nums.length;i++){
dp[i] = Math.max(nums[i],dp[i - 1] + nums[i]);
}
int res = Integer.MIN_VALUE;
for(int i = 0 ; i < nums.length;i++){
res = Math.max(res,dp[i]);
}
return res;
}
}
其实我看到这个题目首先想的也是滑动窗口,因为滑动窗口最适合解决求连续的子串、子数组等问题,但是这个数组元素里面有负数,用滑动窗口是做不出来的,因为改变窗口左右指针的条件不明确。
题目二、题目三属于同一类动态规划问题。
边栏推荐
- Pycharm remote execution
- 【OpenCV 例程200篇】220.对图像进行马赛克处理
- Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
- 20220211 failure - maximum amount of data supported by mongodb
- Reviewer dis's whole research direction is not just reviewing my manuscript. What should I do?
- What's the best way to get TFS to output each project to its own directory?
- El table table - get the row and column you click & the sort of El table and sort change, El table column and sort method & clear sort clearsort
- 3D人脸重建:从基础知识到识别/重建方法!
- Redis insert data garbled solution
- It's almost the new year, and my heart is lazy
猜你喜欢
KDD 2022 | 通过知识增强的提示学习实现统一的对话式推荐
Laravel notes - add the function of locking accounts after 5 login failures in user-defined login (improve system security)
【滑动窗口】第九届蓝桥杯省赛B组:日志统计
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
HMS Core 机器学习服务打造同传翻译新“声”态,AI让国际交流更顺畅
What key progress has been made in deep learning in 2021?
Performance test process and plan
OneNote in-depth evaluation: using resources, plug-ins, templates
The most comprehensive new database in the whole network, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, flying Book Multidimensional table, heipayun, Zhix
随机推荐
[MySQL] basic use of cursor
@GetMapping、@PostMapping 和 @RequestMapping详细区别附实战代码(全)
Pat 1078 hashing (25 points) ⼆ times ⽅ exploration method
Xcode6 error: "no matching provisioning profiles found for application"
2022菲尔兹奖揭晓!首位韩裔许埈珥上榜,四位80后得奖,乌克兰女数学家成史上唯二获奖女性
【深度学习】PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
字符串的使用方法之startwith()-以XX开头、endsWith()-以XX结尾、trim()-删除两端空格
What is the difference between procedural SQL and C language in defining variables
Seven original sins of embedded development
Hardware development notes (10): basic process of hardware development, making a USB to RS232 module (9): create ch340g/max232 package library sop-16 and associate principle primitive devices
Ravendb starts -- document metadata
Pat 1085 perfect sequence (25 points) perfect sequence
KDD 2022 | 通过知识增强的提示学习实现统一的对话式推荐
[sliding window] group B of the 9th Landbridge cup provincial tournament: log statistics
Forward maximum matching method
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
Nodejs教程之Expressjs一篇文章快速入门
KDD 2022 | realize unified conversational recommendation through knowledge enhanced prompt learning
Web开发小妙招:巧用ThreadLocal规避层层传值
None of the strongest kings in the monitoring industry!