有没有近期RENEW过EAD和AP的 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

有没有近期RENEW过EAD和AP的

有没有近期RENEW过EAD和AP的# EB23 - 劳工卡

p*o2014-06-20 07:06

1 楼

这两天在专攻DP，慢慢的有了一些理解，在这里写一写，如果领悟正确可以帮跟我一样
挣扎的人省些时间，如果不对正好可以请高手指点。
个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
LeetCode的问题，Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS，如果两
条路径共享一部分的话，共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
索的问题，从而达到节省一部分时间的目的。对于这个题目，DP不能提高时间复杂度，
因为这题本来就是NP-complete －－不论用什么方法，所有路径都被看一遍才能知道结
果。但是由于prune掉很多不必要的搜索，还是可以提高效率。

s*32014-06-20 07:06

2 楼

我们这是第二次RENEW。去年那次很快，几乎邮寄出去就收到RECEIPTS了，然后差不多
一个月就下来了。年初搬了家，但立刻去USCIS做了地址变更，也收到确认了。可是这
次邮寄出了EAD/AP申请两周还没有收到RECIEPTS，有点毛。AP倒是不急，EAD8月中旬到
期，现在看讨论好像都不快，心里不踏实，上来问问。。。有类似经历的分享一下，谢
谢了先。

t*h2014-06-20 07:06

3 楼

牛人啊，膜拜

d*u2014-06-20 07:06

4 楼

首先要判断这个问题能不能用dp来解，也就是是否存在最优子结构。
如果存在最优子结构，那么剩下的就是想出状态转移方程了。

p*o2014-06-20 07:06

5 楼

哇，看来没有基础还是不行啊，大侠两个词就把我彻底打败了。

【在 d**u 的大作中提到】

: 首先要判断这个问题能不能用dp来解，也就是是否存在最优子结构。
: 如果存在最优子结构，那么剩下的就是想出状态转移方程了。

p*o2014-06-20 07:06

6 楼

一点都不牛，看你楼下我楼上

【在 t**********h 的大作中提到】

: 牛人啊，膜拜

p*22014-06-20 07:06

7 楼

对于这个题目，DP不能提高时间复杂度
这句话有大牛confirm吗？

r*e2014-06-20 07:06

8 楼

according to my notes, there are two main types of DP: memoization and
bottom-up.
use a table is the first approach but it's typically slower than bottom-up
based method.
Of course, it is the easiest and maybe the only way to solve a lot of
examples.

【在 p*****o 的大作中提到】

: 这两天在专攻DP，慢慢的有了一些理解，在这里写一写，如果领悟正确可以帮跟我一样
: 挣扎的人省些时间，如果不对正好可以请高手指点。
: 个人感觉DP的要点是在通过caching来减少搜索的次数。比如上次我在这里问的那个
: LeetCode的问题，Unique Paths II。首先考虑不用DP而用简单的DFS或者BFS，如果两
: 条路径共享一部分的话，共享的这部分就会被搜索两次。而用DP就可以克服这个重复搜
: 索的问题，从而达到节省一部分时间的目的。对于这个题目，DP不能提高时间复杂度，
: 因为这题本来就是NP-complete －－不论用什么方法，所有路径都被看一遍才能知道结
: 果。但是由于prune掉很多不必要的搜索，还是可以提高效率。

p*o2014-06-20 07:06

9 楼

For this specific problem (Unique Paths II), how does a bottom-up solution
work? I have tried to use a bottom-up method, but soon lost in the mess.

【在 r*****e 的大作中提到】

: according to my notes, there are two main types of DP: memoization and
: bottom-up.
: use a table is the first approach but it's typically slower than bottom-up
: based method.
: Of course, it is the easiest and maybe the only way to solve a lot of
: examples.

d*x2014-06-20 07:06

10 楼

as long as u can figure out the state transfer function...

【在 p*****o 的大作中提到】

: For this specific problem (Unique Paths II), how does a bottom-up solution
: work? I have tried to use a bottom-up method, but soon lost in the mess.

p*o2014-06-20 07:06

11 楼

wow，居然找到了，多谢提醒。

【在 d**********x 的大作中提到】

: as long as u can figure out the state transfer function...

h*e2014-06-20 07:06

12 楼

我觉得CLRS书上DP那一章就讲得很清楚了。那一章后面的题目真是
又臭又长，看清题意都要花不少时间。
DP的题目面试和做Online Judge的主要差别是: 一般面试的时候
由于时间有限，用递归加memoization会好写一些；做Online Judge
的时候，写程序没有时间限制，bottom-up程序运行效率会更高一些，
而且不会担心stack overflow。

d*x2014-06-20 07:06

13 楼

搞久了之后，还是bottom up的好。。

【在 h****e 的大作中提到】

: 我觉得CLRS书上DP那一章就讲得很清楚了。那一章后面的题目真是
: 又臭又长，看清题意都要花不少时间。
: DP的题目面试和做Online Judge的主要差别是: 一般面试的时候
: 由于时间有限，用递归加memoization会好写一些；做Online Judge
: 的时候，写程序没有时间限制，bottom-up程序运行效率会更高一些，
: 而且不会担心stack overflow。

p*o2014-06-20 07:06

14 楼

CLRS是什么书？

【在 h****e 的大作中提到】

p*22014-06-20 07:06

15 楼

不一定吧？看题。

【在 d**********x 的大作中提到】

: 搞久了之后，还是bottom up的好。。

p*o2014-06-20 07:06

16 楼

这句话我收回了，之前是我榆木脑袋想不到。

【在 p*****2 的大作中提到】

: 对于这个题目，DP不能提高时间复杂度
: 这句话有大牛confirm吗？

h*e2014-06-20 07:06

17 楼

Introduction to Algorithms from MIT，CLRS是四位作者姓的首字母。
大概是一本永远看不完的书。

【在 p*****o 的大作中提到】

: CLRS是什么书？

p*22014-06-20 07:06

18 楼

我翻了翻，但啥也没记住呀。

【在 h****e 的大作中提到】

: Introduction to Algorithms from MIT，CLRS是四位作者姓的首字母。
: 大概是一本永远看不完的书。

h*e2014-06-20 07:06

19 楼

你看的是第三版的吗？第15.3节讲可以用DP的必要元素以及解决办法。
当然具体题目发现那些要素并不是容易的事情。我也只是看了纸上谈兵
而已。

【在 p*****2 的大作中提到】

:
: 我翻了翻，但啥也没记住呀。

d*x2014-06-20 07:06

20 楼

不是题目的问题
应用中bottom up的会快。。

【在 p*****2 的大作中提到】

:
: 我翻了翻，但啥也没记住呀。

p*22014-06-20 07:06

21 楼

你看看GCJ Round1 最后一题 bottom up怎么搞？

【在 d**********x 的大作中提到】

: 不是题目的问题
: 应用中bottom up的会快。。

p*22014-06-20 07:06

22 楼

我脑子太笨了， CLRS, programming pearls, careerup 150全买了。啥都没学会。

【在 h****e 的大作中提到】

: 你看的是第三版的吗？第15.3节讲可以用DP的必要元素以及解决办法。
: 当然具体题目发现那些要素并不是容易的事情。我也只是看了纸上谈兵
: 而已。

l*s2014-06-20 07:06

23 楼

我觉得您可以去试试水啦，现在是版面众望所归

【在 p*****2 的大作中提到】

:
: 我脑子太笨了， CLRS, programming pearls, careerup 150全买了。啥都没学会。

d*x2014-06-20 07:06

24 楼

粗看起来和最长公共子序列或者edit distance没有区别
有啥陷阱么。。？

【在 p*****2 的大作中提到】

:
: 我脑子太笨了， CLRS, programming pearls, careerup 150全买了。啥都没学会。

X*K2014-06-20 07:06

25 楼

这个Unique Paths II怎么变成NP-complete了，不是把二维数组过一遍，
复杂度O(mn)吗？

【在 p*****o 的大作中提到】

p*o2014-06-20 07:06

26 楼

我不一开始没想到么，看后来更新。

【在 X*K 的大作中提到】

: 这个Unique Paths II怎么变成NP-complete了，不是把二维数组过一遍，
: 复杂度O(mn)吗？