源博客链接:http://blog.csdn.net/cc_again/article/details/25866971 动态规划一直是ACM竞赛中的重点,同时又是难点,因为该算法时间效率高,代码量少,多元性强,主要考察思维能力、建模抽象能力、灵活度。 动态规划(英语:Dynamic programming,DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态…

2021年5月4日 0条评论 9点热度 阅读全文

问题描述: 有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数。    从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来。如何走才能使得这个和尽量大? 如下图:              1           3   2        4 &nb…

2016年3月30日 0条评论 7点热度 阅读全文

题意 给你m个短字符串和一个长串,问你长串拆分成由短串组成的方法数。 思路 dp[i] 表示从i开始的长串后缀,可以用短串组成的方案数。dp[i] += dp[i+len(x)]  其中x是从i开始的长串后缀的前缀,这个前缀属于短串集合。初始条件dp[n] = 1.            用短串建立Trie树,用长串后缀去在字典树上匹配,找到满足条件的短串,更新dp 注意:Trie树的maxnode要开够!!被这个点WA死了.... #inclu…

2015年4月5日 0条评论 5点热度 阅读全文

所谓最大连续子序列,就是求出给定一串数字中连续的那一段元素和的最大值。 举例如: 给定序列:2 3 -1 4 7  则最大子序列的值应为4+7=11.   先说第一种方法:暴力枚举数组中的元素,不断求和,进行更新即可。可是时间复杂度上一般承受不了。O(n^3)的时间复杂度确实对一般的问题很难接受。   第二种:把a[0]初始化为max值,则枚举n个位置,每次把sum置为0,然后从位置i开始计算从i开始的最大连续子序列和的大小,如果大于max,则更新max。 部分代码如下: inline…

2013年12月2日 0条评论 1点热度 阅读全文