温稚

分类

/ 注册

TA的专栏 19篇文章 1人订阅

动态规划题解

17篇文章 602人学习

小米真题题解

0篇文章 0人学习

递归、回溯

2篇文章 429人学习

全部文章（共19篇）

题解 | #最长不含重复字符的子字符串# 小白思路版来自专栏

//本题用动态规划求解，第一次完完全全按照自己思路实现，记录一下 // dp【n】设为以字符串第n个元素结尾的最长的子字符串 // 本题用hashMap<Character,Integer> 记录暂存的子字符串 // dp[n]的求解思路循环遍历字符串 // 细分为三...

2023-10-08

1 358

题解 | #买卖股票的最好时机(一)# 来自专栏

//本题用动态规划求解，暴力搜索最简单 //设记忆化数组为 dp【i】【j】i为天数 j长度为2 【0】【1】 dp代表了i天所持钱数 //0 代表今天不持股 1代表今天持股 //当今天不持股时，有两种情况：昨天不持股，或者昨天卖出 //状态转移方程为：dp[i][0] = Math.m...

2023-10-07

1 364

题解 | #矩形覆盖# 来自专栏

//本题用动态规划求解 //数学归纳法找规律发现为斐波那契数列 f（n） = f（n-1） + f（n- 2）！（关键） //以此建立状态转移方程求解 import java.util.*; public class Solution { public int rectCover(in...

2023-10-07

1 276

题解 | #跳台阶扩展问题# 来自专栏

//本题用动态规划求解 //果然数学还是卡人，这个题本身没难度，唯一难点就是在状态转移方程 //dp[n]设为到n的跳数 //f(n) = f(n-1) + f(n-2) +....+f(0) //f(n-1) = f(n-2) + f(n-3) +......+f(0) //所以 f（n） = ...

2023-10-07

1 259

题解 | #斐波那契数列#最最经典的动规模板题来自专栏

//个人感觉是动规最符合模板流程的题 //定义记录的数组 dp【n】为f（n）的值 //初始化dp值题给的 n=1/2时f（n）等于1 dp[1]/dp[2] = 1 //构建状态转移方程：题给 f（n） = f（n-2） + f（n-1） //即为 dp[n] = dp[n-1] + d...

2023-10-07

1 336

题解 | #跳台阶# 来自专栏

import java.util.*; //动态规划 //设置dp【n】为到达n阶的跳法数，状态转移方程为dp【n】 = dp【n-1】 + dp【n-2】 //因为n- 2阶和n-1都可以一步跳到n public class Solution { public int jumpFloor...

2023-10-07

1 300

题解 | #连续子数组的最大和(二)# 来自专栏

//本题用动态规划解决 /*和求最长子序列和一样，可以看一下我上一篇文章，仅仅对子序列的长度做了记录设置 right ，left ，maxRight ，maxLeft 分别记录实时左右长度和最长的长度 */ public class Solution { /** * 代码中的类...

2023-10-07

1 309

题解 | #连续子数组的最大和# 来自专栏

//本题用动态规划求解 //本题第一种第二种方法思路大致相似，具体实现不同 //dp【i】和temp一个含义，是以第i个元素结尾的最大子数组的和 //转移方程为：dp[i - 1] > 0 ? dp[i] = dp[i-1] + array[i] : dp[i] = array[i]; /...

2023-10-07

1 300

题解 | #乘积为正数的最长连续子数组# 来自专栏

/*本人动规初学者，勿喷本题解题思路：动规个人理解为寻找最优子结构，即构建状态转移方程，记录重复计算值，减少非必要计算次数本题计算乘积为正数的子数组长度，设置两个数组，分别用于记录0-n中的最长的正负子数组长度，仅仅只判断符号当传入两个数组的输入数组值inits[i]时，判断...

2023-10-05

2 436