摸鱼学大师

题解

未归档(8)

/ 注册

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

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

思路：由题目中给到的信息：数组是double型，可正可负可零，也即是说乘积可能突然变小（正x负）也可能突然变大（负x负）返回的子数组必须是连续的一段这是一道典型的动态规划的题，解题最重要的便是找到状态方程。方法一：动态规划如果设置max[i]表示当前i及之前的乘积最大值，min[i]...

动态规划数组子数组乘积

2021-07-16

2 684

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

思路：从题目中给出的信息：不会是空矩阵，矩阵值都是非负数只能往右或者往下，不能返回，因此路径长度会累加故常用的方法便是递归或者动态规划。方法一：递归法（超时）具体做法：容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径值加上(n,m-1)或者(n-1,m)的矩阵路径即可...

最小路径动态规划递归空间记忆搜索

2021-07-14

0 651

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

思路：题目分析：一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！当青蛙在第n阶往下跳，它可以选择跳1阶到n-1，也可以选择跳2阶到n-2，即它后续的跳法变成了f(n-1)+f(n-...

斐波那契数列动态规划递归跳台阶

2021-07-13

0 658

题解 | #汉诺塔问题# 来自专栏

思路：从题中给出的有效信息：汉诺塔，不需要记录次数，但是需要移动的塔的名字对于汉诺塔，无论在哪座塔上，小盘必须要在大盘上面，因此可以逆向思维从结果考虑，left塔最下面的大盘，必定是left塔仅剩它，而right塔上面又什么东西都没有时才可以移动，则其余n-1个盘都在mid塔上，且顺序为从小...

汉诺塔递归动态规划栈非递归

2021-07-13

2 759