lawn秃了，发现下面有大石头，怎么办？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

lawn秃了，发现下面有大石头，怎么办？

lawn秃了，发现下面有大石头，怎么办？# Living

a*12012-10-05 07:10

1 楼

For a general dynamic programming problem involving making decisions over N
steps (each step may have K possible states), what is the time complexity of
solving the problem? A naive approach is fine, and no need to reduce the
time complexity using advanced techniques. Thanks!

w*e2012-10-05 07:10

2 楼

新房，过了夏天发现有几块地方草死了，拿杆子一桶，发现下面是石头，小的好挖，大
的秃头斑直径超过两feet，后院有坡比较陡，怕挖出来了又搬不走，有没有什么好办法
啊，往上面垫土，少了没用，多了不成一个包了。

j*y2012-10-05 07:10

3 楼

Nk ?

N
of

【在 a*******1 的大作中提到】

: For a general dynamic programming problem involving making decisions over N
: steps (each step may have K possible states), what is the time complexity of
: solving the problem? A naive approach is fine, and no need to reduce the
: time complexity using advanced techniques. Thanks!

H*72012-10-05 07:10

4 楼

挖出来作景观石

l*82012-10-05 07:10

5 楼

你没有说每一步的结果可以由之前的几步算出来。

N
of

【在 a*******1 的大作中提到】

u*q2012-10-05 07:10

6 楼

金色的吗？

a*12012-10-05 07:10

7 楼

How about assuming that all the steps are correlated (i.e., making a
decision in the first step will also influence the decision in the last
decision)? For example, we have 10dollars to spend over ten days to buy some
products that have time-varying daily prices. We need to decide how much to
spend each day in order to maximize the number of products we can buy. Of
course, there may be smart algorithms, but I'm just wondering what is the
time complexity of using a naive approach or very basic dynamic programming.

【在 l*********8 的大作中提到】

: 你没有说每一步的结果可以由之前的几步算出来。
:
: N
: of