Couple of DP problems

1018. A Binary Apple Tree (acm.timus.ru)
This was an easy DP problem. The state of the DP is the following: root of the subtree and how many edges we need, in other words dp[node][need] - is the maximum amount of apples that we can preserve if the root of our tree is at the node and we will leave "need" edges. The only tricky part of this problem is that the given input is not necessarily a rooted tree and so after reading the input you have to construct the tree properly.

1002. Phone number (acm.timus.ru)
Another simple DP problem. Let's say S[1..L] is the first L digits of the call number. Let D[L] be the minimum number of words that we can use to split S[1..L]. Obviously, D[0]=0 and D[L]=INFINITY, if we cannot split S[1..L]. In order to compute D[L] we look at S[L..L], S[L-1..L], S[L-2..L], .. up to S[L-49..L] (because there are no words of length more than 50) and check if there are words that match these substrings. For every word matched we try to improve our D[L] in the following way D[L]=min(D[L],D[J]+1), where J=L-(length_of_currently_matched_word). You also have to figure out a fast way to check whether there exists a word that matches certain S[I..J]. This can be done by either creating a c++ map that associates a certain digit sequence with a word or coding your own hashing in pascal.
Also in order to construct the answer we need remember for each L the value of J that D[L] archives the minimum.