New answers tagged dynamic-programming
0
Consider the first three houses (assuming $n \geq 3$). Any solution does not rob one of them, say the first one (you can enumerate over all three options). The remaining houses form a street, which enables us to solve the problem using a simple dynamic programming: for each $0 \leq i \leq 2$ and $j$, we find out the best solution for the first $j$ houses ...
1
Your attempt sounds specious since your proof does not use any specific property of the objective function, $ S = \sum_{i=2}^{n}| A[i] - A[i-1]| $. Had your proof been correct, there would have been an optimal substructure for any arbitrary objective function we could have defined for $A$, which does not make sense.
To prove the existence of an optimal ...
0
I think the answer is: “You write code to do it”. You have a solution for a similar problem, so you work to understand it, and then you modify it to do what you want.
1
Let $\langle o_1, o_2, o_{m+1}\rangle$ be a non-empty optimal sequence of operations that distributes the chocolates evenly, i.e., such that the final distribution is $[k,k,k, \dots, k]$.
Let $\alpha_i$ be the number of candies given to the $i$-th person by operation $o_{m+1}$ and consider the subsequence of operations $\langle o_1, o_2, \dots, o_m\rangle$. ...
2
The essence of dynamic programming is "it is easier to solve many problems than to solve one problem.". Sometimes, the more problems the easier. Sometimes, it is impossible with less problems.
The approach of dynamic programming is finding/inventing many problems that are similar to each other, solving these similar problems in some order so that ...
0
You may be interested in this implementation: https://github.com/fujimotos/polyleven
1
Congratulation for solving a popular problem independently with a perspective that is rarely seen.
The choice between "ending at $i$" and "starting at $i$" can be dismissed as insignificant, coincidental, and random. They are symmetric to each other.
A similar question could be why we read, write and think from left to right, as shown on ...
Top 50 recent answers are included