摸鱼学大师

题解

未归档(8)

/ 注册

全部文章 / 题解（共84篇）

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

题目主要信息: 给出一个数组表示连续多日的股票价格你可以选择在某一天买入股票，在另一天卖出股票，可以最多买入两次卖出两次，但是第二次买入必须在第一次卖出后，且每天只能进行一次操作假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 具体思路: 这道题与买卖...

C++ 动态规划

2022-02-19

0 658

题解 | #买卖股票的最好时机(二)#

题目的主要信息：给出一个数组表示连续多日的股票价格你可以选择在某一天买入股票，在另一天卖出股票，买卖可以有多次机会，但是同一天只能买或者只能卖假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 方法一：动态规划具体做法：这道题与买卖股票的最好时机（...

C++ 动态规划贪心

2022-02-19

0 456

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

题目的主要信息：给出一个数组表示连续多日的股票价格你可以选择在某一天买入股票，在另一天卖出股票，买卖都只有一次机会，不能在同一天假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 可以看成查找数组中b-a的最大值，其中b必须在a的后面方法一：动态规划...

C++ 动态规划贪心

2022-02-19

0 594

题解 | #打家劫舍(二)# 来自专栏

题目主要信息: 给定一个数组，其中代表每家拥有的钱数小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷数组形成环形，第一家与最后一家相邻求最多能偷到钱数具体思路: 这道题与打家劫舍（一）比较类似，区别在于这道题是环形，第一家和最后一家是相邻的，既然如此，在原先的方案中第一家和最后...

C++ 动态规划

2022-02-19

3 679

题解 | #打家劫舍(一)# 来自专栏

题目主要信息: 给定一个数组，其中代表每家拥有的钱数小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷求最多能偷到钱数具体思路: 或许有人认为利用贪心思想，偷取最多人家的钱就可以了，要么偶数家要么奇数家全部的钱，但是有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷，因此这种方案...

C++ 动态规划

2022-02-19

3 648

题解 | #最小花费爬楼梯# 来自专栏

题目主要信息: 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始一旦支付费用，可以任意选择爬一级或是二级需要求爬到顶楼，即越过数组末尾元素所需要的最小花费可以从下标为0或是1的台阶开始具体思路: 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就...

C++ 动态规划

2022-02-19

4 1057

题解 | #正则表达式匹配# 来自专栏

题目主要信息: 一个正常字符串str，可能为空，只包含小写字母一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’ 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）求str与pattern是否能完全匹配具体思路: 如果是只...

C++ 动态规划

2022-02-19

1 346

题解 | #最长上升子序列(一)# 来自专栏

题目主要信息: 给定一个数组，求其中最长的严格上升子序列的长度子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变严格上升指子序列严格单调递增具体思路: 要找到最长的递增子序列长度，常用方法是动态规划，用dp[i]dp[i]dp[i]表示到元...

C++ 动态规划

2022-02-18

0 406

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

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

C++ 递归动态规划

2022-02-18

0 561

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

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

C++ 动态规划

2022-02-18

3 650