华科不平凡

分类

题解(135)

/ 注册

TA的专栏 135篇文章 8人订阅

刷遍天下无敌手

135篇文章 15888人学习

0篇文章 0人学习

全部文章（共20篇）

蒙德里安的梦想（状态压缩DP）来自专栏

由于长宽都比较小，采用棋盘式状态压缩DP解决，此类任务一般是在棋盘内填各种形状的块，然后求方案数。核心思想是：总方案数等于合法横向摆放小矩形方案数之和。下面的图形中，绿色为横向填充，黄色为纵向填充，图1是合法的，图2则是非法的。设状态矩阵为dp[i][j]，其中i表示第i列，j表示横跨第i-...

状态压缩DP 动态规划

2020-09-29

0 1171

买卖股票的最佳时机iii 来自专栏

利用两个dp数组 dp1[i]表示以第i个元素结尾的子串的最大收益 dp2[i]表示以第i个元素开始的子串的最大收益代码如下： // // Created by jt on 2020/9/24. // #include <vector> using namespace std; ...

动态规划

2020-09-24

3 896

连续子数组的最大和来自专栏

设dp[i]表示0..i以i结尾的连续子数组的最大序列和，那么有如下状态公式：当i=0时，dp[0] = arr[0] 当i>0时，dp[i] = max(dp[i], dp[i]+arr[i-1]) 代码如下： // // Created by jt on 2020/9/18. // ...

动态规划

2020-09-18

0 543

最长递增子序列来自专栏

两步走：第一步——求最长递增子序列长度第二步——求字典序靠前的子序列对于第一步，有两种解法：动态规划，时间复杂度为O(n^2)，会超时贪心+二分，时间复杂度为O(nlogn) 下面说说贪心+二分的解法，举例说明基本思路，假设数组arr为[2, 3, 1, 2, 3]，vec数组里...

贪心二分法动态规划

2020-09-15

107 6676

通配符匹配来自专栏

为了描述方便，我们将s称为主串，p称为模式串三种思路：贪心（超时）回溯动态规划贪心（超时） // // Created by jt on 2020/8/31. // #include <cstring> #include <iostream> using na...

递归贪心动态规划

2020-08-31

6 1332

有障碍的矩阵最短路径数来自专栏

设dp[i][j]表示前i行和前j列最短路径数，状态方程如下：当i >= 2 && j >= 2时，如果obstacle[i-2][j-1] != 1, dp[i][j] += dp[i-1][j] 如果obstacle[i-1][j-2] != 1, dp[i][...

动态规划

2020-08-30

2 1144

矩阵路径数来自专栏

dp[i][j]表示前i行、j列的路径数，状态公式如下：如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[1][k] = 1 dp[k][1] = 1 解释如下：当列数和行数大于2的时候，当前节...

动态规划

2020-08-30

7 1039

带权值的最小路径和来自专栏

设dp[i][j]表示行数为i，列数为j的矩阵中，从左上角到右下角的最小路径和。状态公式：当i>=2 && j>=2时，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1] 基准1: dp[1][k] = dp...

动态规划

2020-08-30

1 1032

爬楼梯来自专栏

两种方法：斐波那契数列（找规律——爬1层1种，2层2种，3层3种，4层5种...）动态规划有必要总结一下找规律的解法：这种解法需要细心和耐心，我们一般取出前3种情况看一下规律，如果规律不明显，可以增加情况，直到过于复杂才放弃此解法。PS：前几种情况同样可以用来检验算法的正确性动态规划...

斐波那契数列动态规划

2020-08-30

0 882

最小编辑距离来自专栏

dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式：如果word1[i-1] = word2[j-1]，dp[i][j] = dp[i-1][j-1] 如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1...

动态规划

2020-08-30

0 1029