辅导dynamic programming、Python，Java编程讲解、辅导c/c++，Java语言
辅导R语言编程|辅导Python编程
4 Homework 3
Deliverables. You should solve the problems in this homework using dynamic programming.
Recall that a dynamic programming solution MUST include
1. A definition of subproblems
2. A recursion, including a base case
3. A bound on the number of subproblems (as in: the number of subproblems is O(n
2k))
4. A bound on the recursion time (as in: the recursion takes time O(n))
Unless explicitly stated otherwise, pseudocode and examples are not required.
Problem 4.1. (Difficulty 3) There are n gold coins placed at positions {1, . . . , n} on a line.
The gold coin at position i has a positive weight wi
. You can pick any of the n coins, except
that if you pick the gold coin at position i then you cannot pick the adjacent ones, that is,
the ones at positions i 1 and i + 1. Design a dynamic programming algorithm to compute
the maximum total weight of the coins you can collect. Also explain how to compute
the sequence of coins to be taken. Make your algorithm as fast as you can.
For example, if n = 3 and the gold coins have weights w1 = 20, w2 = 30, w3 = 15, then
the maximum total weight is 20 + 15 = 35 and is obtained by picking the coins at positions
1 and 3.
Problem 4.2. (Difficulty 3) Bob has to plan his working life for the next T years. There
are m jobs that Bob can do, and every year Bob must do exactly one job. Each job pays
different amounts depending on the year. (For example, being a mail carrier will pay less
and less with time, while being a computer scientist will pay more and more with time.)
Specifically, during a year t a job j pays W(j, t). Bob is currently doing job 1 and can switch
job at most S times.
Give an algorithm to compute the maximum possible earning of Bob for the next T years.
The running time of the algorithms should be polynomial in T, m, and S.
Problem 4.3. (Difficulty 3) [Taken from Jeff Erickson’s book] Vankin’s Mile is an American
solitaire game played on an n × n square grid. The player starts by placing a token on any
square of the grid. Then on each turn, the player moves the token either one square to the
right or one square down. The game ends when player moves the token off the edge of the
board. Each square of the grid has a numerical value, which could be positive, negative,
or zero. The player starts with a score of zero; whenever the token lands on a square, the
player adds its value to his score. The object of the game is to score as many points as
possible.For example, given the grid below, the player can score 8 ?6 + 7?3 + 4 = 10 points
by placing the initial token on the 8 in the second row, and then moving down, down, right,
down, down. (This is not the best possible score for this grid of numbers.)
1. Describe and analyze an efficient algorithm to compute the maximum possible score
for a game of Vankin’s Mile, given the n × n array of values as input.
222. In the European version of this game, appropriately called Vankin’s Kilometer, the
player can move the token either one square down, one square right, or one square left
in each turn. However, to prevent infinite scores, the token cannot land on the same
square more than once. Describe and analyze an efficient algorithm to compute the
maximum possible score for a game of Vankin’s Kilometer, given the n × n array of
values as input.