For.dream

题解

/ 注册

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

题解 | #求正数数组的最小不可组成和#

问题描述给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？解题思路 01背包问题是一个非常经典的动态规划问题，可以很好的入门动态规划，与之相关的变形题目也是非...

2021-06-26

3 878

题解 | #星际密码#

题目牛客解题思路本题的基本意思就是给你给定一个矩阵：，然后一个数n，n表示矩阵的n次方，这个n代表一个数也就是解密的结果，即为n的结果的（也是一个矩阵）的左上角数字。如果该数字小于4就用0补充，如果大于4就只输出最后4位同时矩阵的乘法公式如下：所以先代入前几个数，可以发现如下规律当...

2021-06-25

1 679

题解 | #计算字符串的距离#

题目牛客解题思路这道题属于贪心算法，但本质仍然是动态规划。对于这样一个棋盘，到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到，要么是前一列(i,j-1)向右移动一列得到因此我们可以建立一个相同的矩阵gifts,gifts[i][j]表示从起点到i,j这一点中某条路径代表的礼物...

2021-06-22

4 618

题解 | #计算字符串的距离#

题目 leetCode72:编辑距离编辑距离算法是一个非常实用的算法，它的作用是求出把一个字符串s1变为另一个字符串s2所需要的最少的操作数。此过程中，只能对字符串进行插入、删除或替换（其实还有一种隐形操作，就是略过）比如把rad变为apple，就需要经过5步解题思路（1）基本过程对于...

算法动态规划

2021-06-19

36 1539