Given k different types of envelopes. The dimensions of envelope type i are xi × yi. You can place envelope A inside envelope B if and only if the dimensions A are
strictly smaller than the dimensions of B. how many possible combination you can have?
Build directed graph, do topological sorting then scan from the lowest and calculate: d [u] = sum d [v], where v are u's children.
ReplyDelete