У динамічних програмувальних задачах, коли-небудь важливо, чи починаєте ви з фронту чи ззаду?
Прямо зараз я не думаю ні, тому що навіть в задачах оптимізації, де говорять, fun(n) = some penalty + fun(n-1)тут fun(n-1) не залежить від значення в n. А це означає, що ми могли б дуже добре обчислити fun(n-1) починаючи з самого початку, а потім додав штраф.
Чи можете ви, будь ласка, подаруйте мені приклад.
Відповіді:
2 для відповіді № 1На мій погляд, в контексті динамікипрограмування, "починаючи з задньої" - це просто рекурсія без реального використання динамічного програмування. Якщо результати перехресних підзадач зберігаються в кеш-пам'яті, це називається "memoization", яке досягає однієї складності виконання часу як динамічне програмування, але деякі з них не розглядаються як "динамічне програмування в найсуворішому сенсі". Загалом, "починаючи з фронту" без допоміжної структури даних, для здійснення мемуалізації точно є динамічне програмування консенсусом.
0 для відповіді № 2
Я не думаю, що властивість повернути назадвхід пов'язаний з динамічним програмуванням, у вашому прикладі це пов'язано з комутативною властивістю додавання. Проблема, що ви не можете змінити вхід і отримати той же результат http://en.wikipedia.org/wiki/Longest_increasing_subsequence. І це вирішується за допомогою динамічного програмування.