H****s
发帖数: 247 | 1 用经典DP肯定是O(N^3), 但是用经典递归呢（没有剪枝和caching）?
能想到的是：O(N) = O(N-1) + O(N-2) + O(N-3) + ... + O(1) + N
但怎么解啊？ | H****s
发帖数: 247 | 2 居然没人回答，估计是我的问题太弱了，自己顶，把题目也贴在这里
Given a string s1, we may represent it as a binary tree by partitioning it
to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two
children.
For example, if we choose the node "gr" and swap its two children, it
produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
【在 H****s 的大作中提到】
: 用经典DP肯定是O(N^3), 但是用经典递归呢（没有剪枝和caching）?
: 能想到的是：O(N) = O(N-1) + O(N-2) + O(N-3) + ... + O(1) + N
: 但怎么解啊？
| j*****y
发帖数: 1071 | 3 recursive的 时间代价感觉是
T(n) = 2(T(1) + T(n - 1) + T(2) + T(n - 2) + ... + T(n - 1) + T(1)) =
4(T(1) + T(2) + ... + T(n - 1))
T(n) = O(5^n)
it
【在 H****s 的大作中提到】
: 居然没人回答，估计是我的问题太弱了，自己顶，把题目也贴在这里
: Given a string s1, we may represent it as a binary tree by partitioning it
: to two non-empty substrings recursively.
: Below is one possible representation of s1 = "great":
: great
: / \
: gr eat
: / \ / \
: g r e at
: / \
| H****s
发帖数: 247 | 4 感觉比较靠谱，等我有时间好好算算。
【在 j*****y 的大作中提到】
: recursive的 时间代价感觉是
: T(n) = 2(T(1) + T(n - 1) + T(2) + T(n - 2) + ... + T(n - 1) + T(1)) =
: 4(T(1) + T(2) + ... + T(n - 1))
: T(n) = O(5^n)
:
: it
|
|
