Dynamic programming - maximize sum of functions subject to constraints Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$. 

The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$

I think we suppose to come up with a polynomial time solution, but i got stuck on identifying the sub-problems and using them.

One direction that i had was creating a list for each function, where both the arguments and the function values are in decreasing order: in each iteration, find the argmax of the function, delete bigger arguments that yield smaller function values, and proceed with the smaller arguments that remain (($O(k^3)$ for all functions).

Then  use those lists to iterativly construct the optimal solution under the constraint for 1, 2, .. and finally for all $k$ functions, Got stuck about here. Not sure if it's a good direction at all...

Would appreciate any assistance.
Let us read the objective again, "maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ where $\sum_{i=1}^{k}x_i\le k$."

The subproblems or the table entries are $DP[a][b]$ for all $0\le a\le k$ and $0\le b\le k$, where $DP[a][b]$ is the maximum value of $\sum_{i=1}^{a}f_i(x_i)$ where $\sum_{i=1}^{a}x_i=b$. The wanted maximum sum is the maximum of $DP[k][0],DP[k][1], \cdots, DP[k][k]$.

The base cases is $DP[1][b]=f_1(b)$ for all $b$.

How to reduce the computation of $DP[a][b]$ to smaller subproblems? The following equality is the critical observation, which is the reason why we have the first dimension "[a]" in the formulation of the subproblems. The other dimension "[b]" comes from the constraint $\sum_{i=1}^{a}x_i=b$.

$$\sum_{i=1}^{a}f_i(x_i) = \sum_{i=1}^{a-1}f_i(x_i) + f_a(x_{a}),$$
i.e., $DP[a][b]$ is the maximum of the following numbers,
$$\begin{aligned}
&amp;DP[a-1][b] + f_a(0),\\
&amp;DP[a-1][b-1] + f_a(1),\\
&amp;\cdots,\\
&amp;DP[a-1][0] + f_a(b).\\
\end{aligned}$$



Exercise 1. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le n$, where $n$ is a given integer.

Exercise 2. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i= n$, where $n$ is a given integer.

Exercise 3. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint that for all $j$, $|x_{j+1}-x_{j}|\le n$, where $n$ is a given integer.