Dynamic programming - maximize sum of functions subject to constraints
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.