s********u
发帖数: 1109 | 1 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
s***h
发帖数: 487 | 2 stack-based graph traversal, 在算法模型上，属于 constructive algorithm。
如果把 graph 看成 solution space，也就是 construction based on graph nodes
adjacency。这个本质上没有 Subproblem 的概念，但可以用来实现各种不同的
subproblem 模型，包括 overlapped subprogram ...
: 当然对 graph 而不是 tree，subproblem 之间其实有 overlap，但这个
overlap 属于
: trivial，用个 visited mark 先到先占位就是了。
: traversal
: 所谓
: subproblem 的
: FIFO，以
|
|
z****t
发帖数: 4322 | 3 昨天在飞机上碰到了以前的强森教授，老E给我从deterministic optimization的角度
讲解了一下目前的美国经济形势。
我老灵感大发，决定用operation research的角度讲解一下中国足球，给中国足球解解
盘。这个帖子可能只有学数学和统计优化的能看懂，如果讲解不对zaoqi,drake等内行
也不要嘲笑。
如果说中国足球是一mix integer program的话,我们现在最需要的是an exact
solution to the MIP. 我们山东人前些年就是在用pure enumeration的方式来解，但
是南方人特别是江浙沪一带的却一直在用heuristic来解问题。南方的问题是，从来不
会100%的努力，而总是想些捷径。在场上就知道用脑子来想最优的办法，而不是努力，
努力再努力。就像我说的，南方人上场踢球都带着CPLEX。 就像很多用cplex的人一样
，总是忽略了cplex虽然牛，但是却有很多limitation, 有warm up找到first feasible
solution的时间，可能比我们北方人搞pure enumeration还要时间... 阅读全帖 |
|
b******t
发帖数: 965 | 4 http://en.wikipedia.org/wiki/Dynamic_programming
This can be achieved in either of two ways:[citation needed]
Top-down approach: This is the direct fall-out of the recursive formulation
of any problem. If the solution to any problem can be formulated recursively
using the solution to its subproblems, and if its subproblems are
overlapping, then one can easily memoize or store the solutions to the
subproblems in a table. Whenever we attempt to solve a new subproblem, we
first check the table to s |
|
s***h
发帖数: 487 | 5 当然对 graph 而不是 tree，subproblem 之间其实有 overlap，但这个 overlap 属于
trivial，用个 visited mark 先到先占位就是了。
: Recursive-function-call based graph traversal 跟 stack based graph
traversal
: 在算法概念模型上有不少差别我想。
: Recursive function call 是基于 non-overlapping subproblem 的编程概念。
所谓
: Preorder / inorder / postorder 就是 traverse non-overlapping
subproblem 的
: order。这个数学美，但有局限。
: Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有
FIFO，以
: 及更通用的 priority-queue (heap)。
: ，再说
: 管理而
|
|
s***h
发帖数: 487 | 6 当然 recursive function call 也能实现 overlapping subproblem，如果加参数加
marker 能转变成 non-overlapping subprogram
: stack-based graph traversal, 在算法模型上，属于 constructive algorithm。
: 如果把 graph 看成 solution space，也就是 construction based on graph
nodes
: adjacency。这个本质上没有 Subproblem 的概念，但可以用来实现各种不同的
: subproblem 模型，包括 overlapped subprogram ...
: overlap 属于
|
|
i**********e
发帖数: 1145 | 7 感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没有 remingingNuts.
>> 当 remainingNuts 为零的时候，随即被再次调入 getMaxNuts 函数的时候，不要忘
了有 if (N <= C) 这个 base case 的检查。这时候 N 就是 remaining nuts，也就是
0. 这时候 N <= C 的条件必定满足，然后就检查是不是还有剩下的距离。如果还有的
话，那就返回0，因为马以经走不下去了。
我了解你对递归的不确定而感到困惑。递归的解法就是先从简单的例子开始解，然后由
此获取这个问题 (problem) 中的问题 (subproblems)。递归的难点就在于你怎么从一
个 problem 和另一个 subproblem 里寻找那个关系。只要能证明从这个关系把一个问
题引申到下一个 subproblem，问题就能迎刃而解，不用想的太复杂。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
j********x
发帖数: 2330 | 8 The key difference characteristic of a DP solution is that, in DP,
subproblems may share common sub-subproblems, which is called "overlapping
structure" in literature.
Here, it is clear that to find the longest path, you will have some
overlapped subproblem, since paths may have common nodes.
-1 |
|
t******l
发帖数: 10908 | 9 虽然这个线程已经成为粪坑了，但我还是贴一下为啥对于简单问题比如 AIME level 的
，google 出来的答案的阐述方式不会太好（从教育学观点而言），是因为大多数人对
于简单问题不会走先看答案后作弊的学习方法，否则就成为自动成为父母版推妈群的一
员（也就是只知道答案，但不知道答案这个小破手绢是如何找出来的）。
对于这道题目，我顺着我前面 dynamic programming 的思路继续寻找优化解了一下，
具体而言：
这个 dynamic programming 里，keep 所有不同的 last number 的递增序列，是必须
的。原因是因为 dynamic programming 所对应的 overlapping subproblem 的问题。
而这个 overlapping subproblem 在这题上，具体就是在从前 n 到前 n+1 时，新读进
来的数是不是能够 update 已有的序列，必须要 keep 不同序列的 last number。
而因为这题的要求只是求序列长度，而不是具体的序列，所以只要保存一个 (序列最后
的数字，序列的长度) 的 pair 即可，这... 阅读全帖 |
|
s***h
发帖数: 487 | 10 Recursive-function-call based graph traversal 跟 stack based graph traversal
在算法概念模型上有不少差别我想。
Recursive function call 是基于 non-overlapping subproblem 的编程概念。所谓
Preorder / inorder / postorder 就是 traverse non-overlapping subproblem 的
order。这个数学美，但有局限。
Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有 FIFO，以
及更通用的 priority-queue (heap)。
: 不是叫iteration based traversal么？我没看哪个刷题网上用stack based来讲
，再说
: 了recursive的原理上不还是stack based么？只不过这个stack不用你费脑筋去
管理而
: 已。
|
|
发帖数: 1 | 11 都是一样的
一个把stack放到代码段
一个把stack放到数据段
程序写法不太一样而已
: Recursive-function-call based graph traversal 跟 stack based graph
traversal
: 在算法概念模型上有不少差别我想。
: Recursive function call 是基于 non-overlapping subproblem 的编程概念。
所谓
: Preorder / inorder / postorder 就是 traverse non-overlapping
subproblem 的
: order。这个数学美，但有局限。
: Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有
FIFO，以
: 及更通用的 priority-queue (heap)。
: ，再说
: 管理而
|
|
b******7
发帖数: 79 | 12 最近提了几个题，大家都特别支持,非常感谢！！
Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
assuming we knew that such a solution must exist.
这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
subproblems.
F[N] = 0, 则|F[N-1]| = |S[N]|， 然后每个subproblem A[i] 不过有2个值，应该能
有很巧的方法表示这个。请各位大虾赐教啊！ |
|
K******g
发帖数: 1870 | 13 write a program for placing of n hospitals, in M cities,distance between the
cities should be minimum. write the recursive expression.
Assuming n
this set you have to find set of n cities which have minimum distance.
看上去像DP，但是好像subproblem的解不是更大一个subproblem的解，请大家讨论下 |
|
x******3
发帖数: 245 | 14 没看懂你的解法，
比如这段程序，
if(DiffArray[i]*DiffArray[i+1] < 0)
你只是判断相邻的三个元素是不是zig zag，
但是longest zz subsequence里的元素不一定要相邻
能说下你的subproblem space是什么吗
我的subproblem定义是
给定序列A[1..n]
LCCZ(i) = the length of longest ZZ subsequence ending at A[i]
原题的解LCCZ(A) = max(A[i]) 1<=i<=n |
|
i**r
发帖数: 40 | 15 Hmmm...
I was thinking the question was related to maxmium subarray problem or
subset sum problem. I was probably wrong.
The brutal force solution can achieve O(n^2) time complexity. To find an
O(n) solution, the problem need to be formulated as a recursion on a one-
dimensional subproblem space. I simply fail to see optimal substructures
among the prefix subproblems. Is it really possible to get an O(n) time
solution?
sum |
|
A*********r
发帖数: 564 | 16 为了这道题，专门复习了一下dp,并且把两个帖子的回复都仔细研读了一遍，现在来总
结一下吧。
原题：给定M个数字的从1到N的整数数组，找出一个大小为K的子集，这个子集
的半径定义为最小的pair Distance，让找出最大半径的这样的子集。
首先说如果是brute force, 要从M个数中选出K个数，然后计算每个K子集的半径，找到
最大的那个，复杂度为 C(M,K), 算是exponential的了。。
然后很显然这是个optimization problem (maximize the radius),所以可以考虑用DP.
用DP的最重要的就是找到如何从已知的optimal subproblem, 推导出当前的optimal
state. 对于这个题，就是如何从已知的optimal (K-1)元素的子集的， 得到含有K元素
的optimal的子集。
在回复很多人都知道这一点，如果没有特殊的约束条件，这两个子集可以完全不一样，
也构不成DP中的subproblem了。所以我们要先sort输入数组，这样保证了每一个pair
distance involving i and previo |
|
c*********t
发帖数: 2921 | 17 Dino,
你太牛了。对的。
你能不能说说你的rationale?
你是怎么想到了如果前半部分个数是奇数，第二个subproblem的时候就是从mid开始？
如果前半部分个数是偶数，第二个subproblem的时候就是从mid+1开始？
另外你是如何 figure out 按照前半段的一半的长度来交换的？
比如 a b c 1 2 3 ===> a b 1 c 2 3
谢谢！ |
|
n*******w
发帖数: 687 | 18 recursive的意思是指dp可以写成递归形式吧。
更具体的说，是dp + recursive + backtrace。比ls的那个O(n^2)应该还要好一点。
做法是
1 先把valid的单词存成一个tries
2 从头往尾扫，找到所有valid的单词。比如applepie，假设a和apple都是valid。
3 a和apple都试一试。a的话，subproblem变成了split pplepie。apple的话，
subproblem变成了split pie。
用到了tries来剪枝，同时递归的写dp，面试的时候时间上充裕点。 |
|
j******2
发帖数: 362 | 19 不好意思，确实有点钻牛角尖了。因为没学过所以看了看CLRS一不小心跑题了。
再啰嗦一句，CLRS讲Greedy同DP一样最关键要素是optimal structure for subproblem
，只是greedy先make a choice for this step,再解决subproblem;DP则要根据子问题
来make current choice。所以我觉得所有“求有几种。。。解法”的问题都不是最优
化问题，都不算DP或Greedy。
还是回到正轨继续做题。 |
|
n*******w
发帖数: 687 | 20 试试
2 4 2 100 1 1 1 1 1
这题应该是没法greedy的。每次choice之后有A[i]种可能性，每种可能性之后的
subproblem都可能包含最优解。所以无法保证greedy choice之后的subproblem包含最
优解继续greedy choice。
。
j] |
|
s********u
发帖数: 1109 | 21 我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
，可以在subproblems overlap的时候提高效率。
但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
recursion改写成iteration，就复杂多了。 |
|
s*w
发帖数: 729 | 22 codeeval.com 上的一个题
给n个东西，每个东西有重量和价值，要求在重量小于给定值的时候，尽量价值大
在重量是浮点数的情况下，怎么做 bottomup 的 dp table?
我现在的解是 recursion, 而且没 memorization, 因为不知道怎么存这个 table.
帖下代码，请指教一下
#include
#include
#include
#include
#include
#include
using namespace std;
class Solution {
int weightLimit;
int n;
vector weights;
vector costs;
public:
Solution(const string &line) {
istringstream iss(line);
iss >> weightLimit;
int in... 阅读全帖 |
|
d******l
发帖数: 98 | 23 建议楼主看看 CLRS那本书。。
其实DP 与 Divide-and-Conqur 很接近，就是没有重复的subproblem的，就属于Divide
-and-Conqur范围了，DC的subproblem是disjoint的，就是分类讨论的那种，，然后加
上 recursion。。 |
|
i***u
发帖数: 89 | 24 来自主题: JobHunting版 - f家店面题 请搞清楚贪心和dp区别再来发言
We can make whatever choice seems best at the moment and then solve the
subproblems that arise later. The choice made by a greedy algorithm may
depend on choices made so far but not on future choices or all the solutions
to the subproblem. It iteratively makes one greedy choice after another,
reducing each given problem into a smaller one. In other words, a greedy
algorithm never reconsiders its choices. This is the main difference from
dynamic programming, which is exhaustive an... 阅读全帖 |
|
i***u
发帖数: 89 | 25 来自主题: JobHunting版 - f家店面题 请搞清楚贪心和dp区别再来发言
We can make whatever choice seems best at the moment and then solve the
subproblems that arise later. The choice made by a greedy algorithm may
depend on choices made so far but not on future choices or all the solutions
to the subproblem. It iteratively makes one greedy choice after another,
reducing each given problem into a smaller one. In other words, a greedy
algorithm never reconsiders its choices. This is the main difference from
dynamic programming, which is exhaustive an... 阅读全帖 |
|
z****j
发帖数: 111 | 26 RT， dynamic programming is a method for solving complex problems by
breaking them down into simpler subproblems. It is applicable to problems
exhibiting the properties of overlapping subproblems[1] and optimal
substructure.
重叠子问题很好理解，但是，能够应用于DP解决的问题一定要有optimal substructure
吗？就好比Fibonacci所谓的DP解法，只是用了个memo记录下了之间计算过得结果以避
免子问题的重复计算， 但是貌似看不出有什么最优子结构啊。求指点... |
|
P***t
发帖数: 1006 | 27 Tell me how you define subproblem here. And how your subproblem will be used
more than once to solve bigger problems.
of |
|
T******n
发帖数: 42 | 28 新人，问一道算法的作业。
Consider the problem of storing n books on shelves in a library. The
order of the books is fixed by the cataloging system and so cannot be
rearraged. Therefore, we can speak of a book bi, where 1 <= i <= n, that
has a thickness ti and height hi. The length of each bookshelf at this
library is L. Now consider the case where the height of the books is not
constant, but we have the freedom to adjust the height of each shelf to
that of the tallest book on the shelf. Thus the cost of a... 阅读全帖 |
|
l********e
发帖数: 220 | 29 http://en.wikipedia.org/wiki/Dynamic_programming
In mathematics and computer science, dynamic programming is a method for
solving complex problems by breaking them down into simpler subproblems. It
is applicable to problems exhibiting the properties of overlapping
subproblems which are only slightly smaller[1] and optimal substructure (
described below). When applicable, the method takes far less time than naive
methods. |
|
t******l
发帖数: 10908 | 30 另外比如 dynamic programming 是著名的以难题著称。。。但是如果没有马工学的
optimal substructure 和 overlapping subproblem 理论的话，仅仅依靠 raw brain
power 在纸上画所见即所得来规约的话，raw brain power 想上一个礼拜咋的也再也想
不动了不是。。。没有马工理论抽象规则规约试图发现可乘之机的话，很难可持续发展
是真的。。。因为 raw brain power 有生理学限制。
当然有数学马工理论，还是会时而不时的阴沟翻船。。。人之常情。。。但数学马工理
论可持续发展的意义就是，东翻翻，西翻翻，说不定哪天手气一好就翻出来了。。。
: 另外窝觉得有必要批评一下 Facebook interview education 那个小妞的 anti-
math
: 的观点。
: 我不是说 raw brain power 不重要，但 raw brain power 的最大问题是不能积
累，只
: 能走短平快，走火入魔的话也只能是孔乙己型天外飞仙题。。。举个例子就是
text
<... 阅读全帖 |
|
s***h
发帖数: 487 | 31 属实。比如 dynamic programming 这种高端货，工程实用大部分是用在是在图论算法
，比如优化路径，这种半连续准两维空间里的图论算法。
主要是 solution space 太大无法遍历，又有类似欧几里德距离这种空间 pattern 可
利用。
而这类问题里，overlapping subproblems 是 nature of the problem，导致 dynamic
programming 的思想（不一定具体技术）深入人心。
一维 sequence 上的 dynamic programming 更适于是 ACM-ICPC 竞赛题，因为一维空
间的 sequence 的坑爹，常常是自古华山一条路，适合竞赛题。如果是双变量，30% 概
率卡壳。实际上工程上也很少在一维 sequence 上用 dynamic programming，pattern
matching 更实用。不常做竞赛题更容易卡壳。
经验就是，简历上经验里写图论算法路径算法就行了，不需要写 dynamic programming
，否则可能会被问 sequence 上的 dynamic programm... 阅读全帖 |
|
s***h
发帖数: 487 | 32 一样是因为我们没有可以直接实现 recursive function call 的机器，底层都是
stack 实现。
: 都是一样的
: 一个把stack放到代码段
: 一个把stack放到数据段
: 程序写法不太一样而已
: traversal
: 所谓
: subproblem 的
: FIFO，以
|
|
a**********s
发帖数: 588 | 33 1. After ruling out 1/8, you proceed by 7 subproblems each of scale N^3/8.
So
f(N^3) = 7*f(N^3/8)+O(1)
The total complexity is O(log_{8/7}N^3) = O(lgN)
2. Just forget about these cases :) |
|
g*******y
发帖数: 1930 | 34 state: A[i][j][k]
1<=i<=D: A[i]: subproblem from 1th digit to ith digit
-7D<= j <= 7D: you can add/remove j matches
0<= k <= K: the number of moves you've made
value of A[i][j][k] = number of distinct integers
result: sum of A[D][0][所有k]
对ith digit， 它有可能转变到其他的9个(加自身10个)数字 by move x matches +
add/remove y matches
加一个10*10的matrix记录任意两个数字之间的变化
这样就有状态方程了 |
|
n*******s
发帖数: 482 | 35 just wake up and consider it again:
Trying to solve it in this way:
original problem: a1, a2, ....ai, ...an-1, an
subproblem : a1, a2, ... ai
Define array: L[2][n]
L[0][i] --> the max donation where the ith neighbor won't donate
L[1][i] -->the max donation where the ith neighbor will donate
Recursive relation:
L[0][i+1] = max {L[0][i], L[1][i]}
L[1][i+1] = L[0][i] + a[i]
However, during this extension, we don't consider the head/tail collision, but this will be problem. So at the final st |
|
g*******y
发帖数: 1930 | 36 how about
note: inf = infinity
numbers: inf, inf/2,.....10,inf*0.75
all your L[0][] L[1][] will select the first number:"inf"
when it comes to the last number "inf*0.75"：
which number to sacrifice？
obviously the answer should abandon the first "inf", but if you abandon the first number, your L[][] result will become useless
this is exactly what I meant in my post:
You don't define a "state"(i.e,subproblem) well enough if you don't specify whether the first number is chosen or not. |
|
b****r
发帖数: 1272 | 37 先做预处理，对每个点算出H[i] 然后把每一行当做底，把这个Histogram当做
subproblem来解行不
行 |
|
B*****t
发帖数: 335 | 38 可以用堆来做，复杂度O(nlogk)
这题overlapping 的subproblems不好定义，DP好像不是很适合
smallest window
you know
have a list
propose an |
|
A*********r
发帖数: 564 | 39 原题如下：
Imagine you have a square matrix, where each cell is filled with either
black or white. Design an algorithm to find the maximum subsquare such that
a ll four borders are filled with black pixels.
http://careercup.com/question?id=2445
大家都知道这是那道找全部为1的最大子方阵的变形（用DP可以达到O(N^2))，可是这道
题却不太能用那道题的方法，从optimal subproblem 无法得到下一个最优解。
CareerCup上给出了一种答案，也就是找出每一个可能的子方阵，然后测试它的四个边
是否满足条件。。这个首先不是DP, 另外他claim算法复杂度是O(N^2), 可是我怎么看
着像O(N^3),因为每找出一个子方阵，需要O(N^2), 但是对每一次方阵进行测试，也是
需要最坏O(N)的，请大家讨论讨论。。
给个例子
1 1 1 1 1 |
|
F**r
发帖数: 84 | 40 two key attributes for DP, optimal substructure and overlapping
subproblems. tell why this is not DP? |
|
d*******d
发帖数: 2050 | 41 这个问题要考虑分治后每个subproblem的奇偶问题.
你自己再研究研究,不行我再贴code |
|
a***r
发帖数: 93 | 42 这题如果用DP来做，哪位给分析一下什么是subproblem？
【 以下文字转载自 Programming 讨论区 】
发信人: minisand (老婆是A+海博), 信区: Programming
标 题: 请教一个字符串比较排序的问题
发信站: BBS 未名空间站 (Mon Nov 9 16:35:46 2009, 美东)
之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
... 阅读全帖 |
|
y*******g
发帖数: 6599 | 43 来自主题: JobHunting版 - 一个算法题 搜索图的时候信息本来就在node里面
你说的dp用什么subproblem? |
|
n*******w
发帖数: 687 | 44 典型的dp。
Generalize这个问题。把n个数divide成k个group。使得和最小。
根据CLRS上的说法，
Complete Choice Property是，最后一个group从哪个index开始。假设从i。
Subproblem变成把前i-1个数divide成k-1个group。 |
|
n*******w
发帖数: 687 | 45 不还是那样做么。
假设a不可以等于b。这个无关紧要，只影响dp的下标，不影响dp的使用。
1）把0到N分成3部分。
那么第三部分b的取值可能性有哪些。b可以取2到N。假设b=j，第三部分为j-N
2）剩下0到j，要分成2部分。
2）是1）的subproblem，所以可以dp。
recurrence是
D（i, k） = min {D(j, k-1) + f(j, i)}
k-1=
D（i，k）意思是把0到i分成k部分。
这个题是要得到D（N，3）。需要3N的空间，复杂度O(N)。
b, |
|
g****y
发帖数: 240 | 46 DP 用recursion也可以，那就是top down。一般都用iteration，也就是bottom up。
Programming其实是table的意思。所以DP可以理解为你是否用table记录了subproblem
的结果。 |
|
|
w*********0
发帖数: 48 | 48 如果我理解的对的话，dynamic programming有top down和bottom up两种，分别在
recursion和iteration中记录subproblem结果
很多情况下我只能做到top down的，bottom up的怎么想都不直观。但是效率的话，应
该是bottom up好一些吧。。。
发现150题里大部分这种问题都是用的top down。但是我们学校开的一门算法课，大部
分给的例子都是bottom up的。
大家觉得有必要一定写成bottom up么？或者换一个角度 是不是能iterative解的问题
最好不要recursive解呢？ |
|
g****y
发帖数: 240 | 49 如果有这个条件，那就可以参考matrix multiplication的解法。
c[i，j]: denotes the optimal cost of merging array i to array j
then the subproblem structure can be:
c[i,j] = min(c[i,k] + c[k+1,j] + cost of merging array[i:k] and array[k + 1,
j]) for k = i to j - 1
time complexity: O(n^3)
def merge_array(arrays):
assert arrays
n = len(arrays)
if n == 1:
return 0
c = [[sys.maxsize for j in range(n)] for i in range(n)]
for i in range(n):
c[i][i] = 0
for i in range(1, n):
c[i... 阅读全帖 |
|
n*******w
发帖数: 687 | 50 不是。DP解是n * lgn
1. sort array by ending time （n*lgn time ）
2. 递归式
DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
k
max{k} where end time of A[k] <= start time of A[i]
n个subproblem，找k的时候可以binary search，lgn time
最后还是 n*lgn time
处理i的是时候有三种情况
1. 不使用A[i]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小 |
|
