牛客最菜应届生
牛客最菜应届生
全部文章
题解
归档
标签
去牛客网
登录
/
注册
牛客最菜应届生的博客
全部文章
/ 题解
(共4篇)
题解 | #换钱的最少货币数#
思路 1、动态规划2、计算使用每一种零钱时候的硬币数量(外层是零钱,内层是价值),dp[i]代表i所需的零钱数量,dp[i] = min(dp[i], dp[i-coin]+1)3、注意最后的返回条件 代码 class Solution { public: /** * 最少货币数 ...
动态规划
2021-07-24
0
460
题解 | # 子数组的最大累加和问题 #
思路 1、动态规划 2、dp[i] = dp[i-1]+arr[i]或者dp[i] = arr[i] 代码 class Solution { public: /** * max sum of the subarray * @param arr int整型vector t...
动态规划
2021-07-24
0
302
题解 | #最小编辑代价#
思路 1、动态规划问题,dp[i][j]代表前i个转化到前j个的代价(第i个代表下标为i-1的字符)2、初始化第0行、第0列(边界条件)3、递推公式:当str1[i-1] == str2[j-1]时,dp[i][j] == dp[i-1][j-1]; 当不想等时,取三个情况的最小值4、返回dp[m]...
动态规划
字符串
2021-07-19
0
352
题解 | #接雨水问题#
思路 计算某一个位置处的雨水,就是计算该位置处往左最大高度、往右的最大高度的最小值与当前高度的差 所以思路一就是遍历每一个点,然后求和但是因为时间复杂度大,所以超时 思路二是使用动态规划,创建两个dp数组,代表下标为i处的左侧的最大值(或右侧的最大值,包括其本身),递推公式就是:当前最大高度 = m...
数组
动态规划
2021-07-15
0
335