标签: Dynamic Programming

评分 0, 满分 5 星
0 票

动态规划,dp[i]表示到扫描第i个数字时的方法数,若s[i-1]s[i]可以组成字母,那么dp[i] = dp[i - 1] + dp[i - 2],否则dp[i] = dp[i - 1],注意初始化以及对出现0时非法情况的判断。

评分 0, 满分 5 星
0 票

操作系统助教...抽空5分钟码了码,bug free,每个点有选和不选两种状态,dfs暴力搜了过去。开个空间,记忆化搜索肯定能大幅优化时间,改天补写...

评分 5.00, 满分 5 星
1 票

假设a[n - 1]表示第n个这样的数,则a[0] = 1,显然,更大的丑数只能由小的丑数通过乘以2,3,5得到。维护三个头指针,一个尾指针,头指针h1,h2,h3分别指向a[h1],a[h2],a[h3]分别乘以2,3,5能够比目前得到的最大丑数稍大的最小丑数,尾指针则指向目前最大的丑数。显然,如果乘积小于最大的丑数,那就将头指针后移,否则选择三个值中最小的那个加入队尾,直到尾指针到达目标。

评分 5.00, 满分 5 星
1 票

来看一个很有意思的题目.. 首先是闪过脑海的几个想法:1. 枚举消除顺序?阶乘太过暴力;2. 枚举状态是否消除?指数太过暴力;3. 贪心?不具备最优子结构;4. 枚举子结构然后在子结构中找最优解.. 可以一试。 // 终于考完了分布式数据库.. 发现每一个考试之前的夜晚,我都会脑洞大开,突破天际 ..  

评分 5.00, 满分 5 星
2 票

一个可以很好地考察DP思想和编程技巧的题目。对于每一天来讲有三种状态,买、卖、闲,转移的时候除了考虑状态本身,还要考虑状态之间的时序问题,即需要再对每一种状态添加状态转移的标志位。用当前天数做模2运算可以使各状态间很好的互斥开来。

评分 0, 满分 5 星
0 票

动规,sum[i][j]表示从(0, 0)到(i, j)所有元素的和,开辟辅助空间的情况下O(n^2)可以完成转移,比如sumr[i][j]表示对于某一行i,从第0列到第j列所有元素的和;查询O(1),容斥一下就可以了。下面的程序在空间上其实还可以优化,可优化的地方在程序中做出了注释,很简单,就不做修改了。

评分 0, 满分 5 星
0 票

首尾相连的情况就只需把首尾特殊考虑,做两遍DP。第一遍,不偷盗第一家的,把最后一家偷盗的和不偷盗的结果加入结果集;第二遍,正常偷盗,把不偷盗最后一家的结果加入结果集。结果集中的最大值就是结果,漏掉了总共只有一家的情况,考虑进去就好了。