DP = Dynamic Programming

1 Q1 You are planting a line of apple trees. There are n possible locations (1, 2, ..., n) where you can plant a tree, equally spaced 1 foot apart. You are given an array A[1...n] where A[i] is the number of apples you will get if you plant a tree at location i (some soil is better than others for growing). However, the distance between trees must be at least 10 feet so that the trees do not shade each other. Clearly define the subproblem, i.e., explain in English what each entry of your DP table/array means. Define each variable you introduce. Write a recurrence expressing the solution of the subproblem in terms of smaller subproblems: i.e., write a formula that can be used to calculate the entries of your DP table/array from previous entries. Specify the base case(s). Give an O(n) time dynamic programming algorithm to find the most apples you can grow. Describe your algorithm in pseudocode. Comment your code. Your algorithm must run in O(n) time to receive credit