摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10952人学习

全部文章（共87篇）

题解 | #求路径# 来自专栏

题目的主要信息：给定一个m*n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量每次只能往下或者往右走这道题非常典型，我们可以考虑多种方式。方法一：递归具体做法：首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个(n−1)∗m(n-1)*m(n−1)∗m...

C++ 递归动态规划

2022-02-18

0 600

题解 | #编辑距离(一)# 来自专栏

题目主要信息: 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符求增删改的最少次数，让第一个字符串变成第二个字符串字符串中只出现大小写字母具体思路: 把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转...

C++ 动态规划

2022-02-18

3 653

题解 | #分割等和子集# 来自专栏

题目的主要信息：给定一个只包含正整数的数组，从中取出若干个数，使取出的数之和与剩余数字之和相等方法一：递归及优化具体做法：我们可以求得数组的累加和sum，即只要从数组中选出一个子集的元素，元素之和为sum的一半，那剩余的元素之和就是另一半，则题目就变成了从数组中选择若干个数使其和为目标值...

C++ 动态规划

2022-02-10

4 478

题解 | #跳跃游戏(二)# 来自专栏

题目的主要信息：给定一个非负整数数组，数组中每个元素值表示可以往后续跳跃的最大步数，即到达某个元素值时可以往后跳跃1到该值之间任意步数需要从数组第一个元素跳到数组最后一个元素，其中每经过一个元素，该元素的值作为积分，求最大积分值如果数组为空或者到达不了末尾返回-1 方法一：动态规划具体做...

C++ 动态规划贪心

2022-02-10

1 605

数组题目技巧总结（四）来自专栏

数组题目介绍数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与各类算法结合的问题B篇。问题类型与技巧数组与贪心算法的问题贪心算法的宗旨在于每次每次都能到...

数组动态规划贪心算法

2022-02-06

0 392

题解 | #矩阵的最小路径和# 来自专栏

题目主要信息: 给定一个矩阵，从矩阵左上角到右下角，每次只能向下或者向右从左上角到右下角路径上经过的所有数字之和为路径和，求该路径和的最小值矩阵不为空，每个元素值都为非负数具体思路: 最朴素的解法莫过于枚举所有的路径，然后求和，找出其中最大值。但是像这种有状态值可以转移的问题，我们可以尝试...

C++ 数组动态规划

2022-02-05

0 458

题解 | #子数组最大乘积# 来自专栏

题目主要信息: 给定一个double型数组，数组元素可正可负可0 需要找到连续子数组每个元素相乘的最大值具体思路: 因为数组元素有正有负有0，因此如果我们用max[i]max[i]max[i]表示当前下标iii及之前的子数组乘积最大值，min[i]min[i]min[i]表示当前下标iii及之...

C++ 数组动态规划

2022-02-05

0 496

题解 | #兑换零钱(一)# 来自专栏

题目的主要信息：给定数组arr，arr中所有的值都为正整数且不重复 arr中每个值代表一种面值的货币，每种面值的货币可以使用任意组成aim的最少货币数如果无解，请返回-1 方法一：空间记忆递归具体做法：对于需要凑成aimaimaim的钱，第一次我们可以选择使用arr[0]arr[0]a...

C++ 递归动态规划

2021-12-09

1 708

题解 | #最大正方形# 来自专栏

题目的主要信息：给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积输入的矩阵是字符形式而非数字形式方法一：动态规划具体做法：对于这类区间内找最大某某值的问题，一般采用动态规划。可以用dp[i][j]dp[i][j]dp[i][j]表示以[i,j][i...

C++ 动态规划

2021-12-09

1 470

题解 | #最长的括号子串# 来自专栏

题目的主要信息：一个长度为nnn的仅包含左右括号的字符串计算最长的格式正确的括号子串的长度方法一：栈具体做法：可以使用栈来记录左括号下标，每次遇到右括号则弹出左括号的下标，然后长度则更新为当前下标与栈顶下标的距离。因为遇到不符合的括号，可能会会使栈为空，因此需要使用start记录上一次...

C++ 栈动态规划字符串

2021-12-07

0 347