# Dynamic programming problem and shortest path problem

I was wondering

1. if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and sink nodes given? And vice versa?
2. Is any dynamic programming problem essentially a linear integer programming problem?
3. if in a network, the shortest path length between every vertices defines a metric on the set of vertices of the network?

Thanks and regards!

-

## 1 Answer

For the first part of (1): The answer is no. The simplest example off the top of my head is the longest substring of ones in a 0,1 string. The typical DP solution would be to use a 1D array and store the length of the longest substring up that includes the $i$-th character in the $i$-th coordinate.

For the vice-versa part of (1): Yes.

The not-so-direct answer for (1) and (2) is that dynamic programming should be seen as a method and not a set of problems. It just describes a general paradigm for solving problems by memoizing solutions to subproblems and building on them. In that sense, it really is some kind of extension of greedy algorithms, only that it can build on multiple subproblems instead of just one in the case of greedy algorithms.

For part (3): This holds for finite undirected graphs with positive weights. It also holds for countably infinite graphs, but does not hold in general for graphs of larger cardinality.

-

Thanks! (1) why is the example not able to be formulated into a source-sink shortest path problem in  a network? (2) Do you mean a DP problem is able to be formulated as an integer programming problem, but not always a linear one? (3) why the shortest path length may not be a metric for infinite graphs and directed graphs? – Tim May 3 '11 at 18:41
For (1) I don't really see an easy way of doing it as a source-sink SPP. For the DP solution, the answer is obtained by scanning the array for the largest number. – Cong Han May 3 '11 at 18:44
For (2) No. DP is a method for designing algorithms. Not a class of problems. – Cong Han Aug 2 '11 at 5:23
For (3). directed doesn't work. Metric needs symmetry. – Cong Han Aug 2 '11 at 5:24
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.934573769569397, "perplexity_flag": "head"}