Суть динамического программирования по-прежнему заключается в рекурсивном алгоритме, но это рекурсивный алгоритм, отвечающий определенным условиям; динамическое программирование — это идея проектирования алгоритма с сильным чувством дизайна и сильным чувством искусства.
Что такое динамическое программирование
определение
Исходная проблема разбивается на несколько подзадач, и ответы на подзадачи сохраняются одновременно, так что каждая подзадача решается только один раз, и в конечном итоге получается ответ на исходную задачу.
- Сначала мы решаем задачу с небольшим объемом данных, а затем рекурсивно решаем задачу с большим объемом данных, обычно этот процесс называется динамическим программированием. Это время сравнимо со сложностью мемоизированного поиска, но в динамическом программировании нет ни рекурсивных вызовов, ни дополнительных вызовов, ни стекового пространства.
- Динамическое программирование — это идея разработки алгоритма с сильным чувством дизайна и сильным чувством искусства.
простой пример
#include <iostream>
#include <ctime>
using namespace std;
int num = 0;
int fib( int n ){
num ++;
if( n == 0 )
return 0;
if( n == 1 )
return 1;
return fib(n-1) + fib(n-2);
}
int main() {
num = 0;
int n = 42;
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
cout<<"run function fib() "<<num<<"times."<<endl;
return 0;
}
анализировать
Через время мы обнаружим, что этот алгоритм очень медленный, почему это решение настолько неэффективно? Когда нам нужно вычислить fib(5), его дерево рекурсии выглядит так:
Из этого рисунка видно, что много повторяющихся вычислений. Как этого избежать? Можно сделать массив memo вне программы. По сути, memo[i] запоминает i-ю последовательность Фибоначчи.
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
vector<int> memo;
int num = 0;
// 记忆化搜索
int fib( int n ){
num ++;
if( n == 0 )
return 0;
if( n == 1 )
return 1;
if( memo[n] == -1 )
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
int main() {
num = 0;
int n = 42;
memo = vector<int>(n+1,-1);
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
cout<<"run function fib() "<<num<<"times."<<endl;
return 0;
}
Мы используем мемо-массив для запоминания, поэтому он называется мемоизированным поиском. Поиск в памяти фактически добавляет планирование в рекурсивный процесс, который является решением сверху вниз.Мы предполагаем, что основная проблема решена, и мы уже задали fib(n-1) и fib(n-2), тогда мы может найти энное число.
Если мы можем решать проблемы сверху вниз, мы также можем решать проблемы снизу вверх, но во многих случаях мы привыкли к первому.
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
// 动态规划
int fib( int n ){
vector<int> memo(n+1, -1);
memo[0] = 0;
memo[1] = 1;
for( int i = 2 ; i <= n ; i ++ )
memo[i] = memo[i-1] + memo[i-2];
return memo[n];
}
int main() {
// 结果会溢出,这里只看性能
int n = 1000;
time_t startTime = clock();
int res = fib(n);
time_t endTime = clock();
cout<<"fib("<<n<<") = "<<res<<endl;
cout<<"time : "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
return 0;
}
Первая задача динамического программирования
литкод 70. Подъем по лестнице
Идеи решения проблем
Давайте рассмотрим идею рекурсии, разбивая большую проблему на маленькие проблемы.
Реализация кода (рекурсивная)
#include <iostream>
#include <vector>
using namespace std;
// 记忆化搜索
class Solution {
private:
vector<int> memo;
int calcWays(int n){
if( n == 0 || n == 1)
return 1;
if( memo[n] == -1 )
memo[n] = calcWays(n-1) + calcWays(n-2);
return memo[n];
}
public:
int climbStairs(int n) {
memo = vector<int>(n+1,-1);
return calcWays(n);
}
};
Реализация кода (динамическое программирование)
Мы обнаружим, что, как и Фибоначчи выше, его можно легко преобразовать в решение для динамического программирования.
#include <iostream>
#include <vector>
using namespace std;
// 动态规划
class Solution {
public:
int climbStairs(int n) {
vector<int> memo(n+1, -1);
memo[0] = 1;
memo[1] = 1;
for ( int i = 2; i <= n; i++ ) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
};
аналогичная проблема
- leetcode 120
- leetcode 64
Найдите пересекающиеся подзадачи
leetcode 343. Целочисленное разбиение
Идеи решения проблем
Если нет идеи для проблемы, мы можем сначала рассмотреть насильственное решение. Другими словами, какой метод мы используем для перечисления всех делений натурального числа n, мы не можем знать, сколько циклов, обычно нам нужно использовать рекурсивные средства.
Решение грубой силы: поиск с возвратом перебирает все возможности деления числа. О (2 ^ п)
Дерево рекурсии существует, потому что оно имеет оптимальную подструктуру
Найдя оптимальное решение подзадачи, можно получить оптимальное решение исходной задачи.
оптимальное основание
- Найдя оптимальное решение подзадачи, можно получить оптимальное решение исходной задачи.
Код
Реализовать 1
#include <iostream>
#include <cassert>
using namespace std;
class Solution {
private:
int max3( int a , int b , int c ){
return max( a , max(b,c) );
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger( int n ){
if( n == 1 )
return 1;
int res = -1;
for( int i = 1 ; i <= n-1 ; i ++ )
res = max3( res , i*(n-i) , i * breakInteger(n-i) );
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1 );
return breakInteger(n);
}
};
реализация 2
Он содержит перекрывающиеся подзадачи, вот запомненная версия поиска:
class Solution {
private:
vector<int> memo;
int max3( int a , int b , int c ){
return max( a , max(b,c) );
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger( int n ){
if( n == 1 )
return 1;
if( memo[n] != -1 )
return memo[n];
int res = -1;
for( int i = 1 ; i <= n-1 ; i ++ )
res = max3( res , i*(n-i) , i * breakInteger(n-i) );
memo[n] = res;
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1 );
memo = vector<int>(n+1, -1);
return breakInteger(n);
}
};
Реализовать 3 динамического программирования
Ниже мы используем восходящий подход, также известный как динамическое программирование, для решения этой проблемы.
class Solution {
private:
int max3( int a , int b , int c ){
return max(max(a,b),c);
}
public:
int integerBreak(int n) {
// memo[i] 表示将数字i分割(至少分割成两部分)后得到的最大乘积
vector<int> memo(n+1, -1);
memo[1] = 1;
for ( int i = 2; i <= n; i++ ) {
// 求解memo[i]
for ( int j = 1; j <= i-1; j++ ) {
// j + (i-j)
memo[i] = max3( memo[i], j*(i-j), j*memo[i-j] );
}
}
return memo[n];
}
};
аналогичная проблема
- leetcode 279
- leetcode 91
- leetcode 62
- leetcode 63
Определение состояний и переходов состояний
буквенный код 198. лут
Определенное состояние
Рассмотрим кражу домов в диапазоне [x...n-1] (определение функции)
переход состояния
f(0) = max{ v(0) + f(2), v(1) + f(3), v(2) + f(4),..., v(n-3) + f(n- 1), v(n-2), v(n-1)} (уравнение перехода состояний)
Идеи решения проблем
Прежде всего, если нет идеи, сначала рассмотрите насильственное решение. Проверьте все дома, для каждой комбинации проверьте, есть ли соседний дом, если нет, запишите его значение и найдите максимальное значение. О ((2 ^ п) * п)
Обратите внимание на определение состояния:
Рассмотрим кражу дома в диапазоне [x ... n-1] (определение функции)
По определению состояния определяется переход состояния:
f(0) = max{ v(0) + f(2), v(1) + f(3), v(2) + f(4),..., v(n-3) + f(n- 1), v(n-2), v(n-1)} (уравнение перехода состояний)
На самом деле наша рекурсивная функция реализует переходы между состояниями.
198. House Robber
код реализации
class Solution {
private:
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
vector<int> memo;
// 考虑抢劫nums[index...nums.size())这个范围的所有房子
int tryRob( vector<int> &nums, int index){
if( index >= nums.size() )
return 0;
if( memo[index] != -1 )
return memo[index];
int res = 0;
for( int i = index ; i < nums.size() ; i ++ )
res = max(res, nums[i] + tryRob(nums, i+2));
memo[index] = res;
return res;
}
public:
int rob(vector<int>& nums) {
memo = vector<int>(nums.size(), -1);
return tryRob(nums, 0);
}
};
Решение для динамического программирования
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if( n == 0 ) {
return 0;
}
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
vector<int> memo(n, 0);
memo[n-1] = nums[n-1];
for( int i = n-2 ; i >= 0 ; i -- ) {
for (int j = i; j < n; j++) {
memo[i] = max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0) );
}
}
return memo[0];
}
};
другое определение государства
Подчеркнем, что для динамического программирования у нас должно быть четкое определение собственного состояния, в определении, прежде чем мы учтем, что мы собираемся украсть [x ... n-1] диапазон дома (определенные функции). Для одной и той же задачи много раз мы можем настроить разные состояния, чтобы получить один и тот же правильный ответ.
Измените определение состояния:
Рассмотрим кражу дома (определение функции) в диапазоне [0...x]. Реализация выглядит следующим образом:
Реализация кода поиска в памяти
class Solution {
private:
vector<int> memo;
//考虑偷取[0..x]范围里的房子
int tryRob(vector<int>&nums, int index){
if (index < 0){
return 0;
}
if (memo[index] != -1){
return memo[index];
}
int res = 0;
for( int i = index; i >= 0; i--){
res = max(res, nums[i] + tryRob(nums, i - 2));
}
memo[index] = res;
return res;
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
memo = vector<int>(n + 1, -1);
if (n == 0){
return 0;
}
return tryRob(nums, n-1);
}
};
Реализация кода динамического программирования
class Solution {
public:
//考虑偷取[0..x]范围里的房子
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> memo(n, -1);
if (n == 0){
return 0;
}
memo[0] = nums[0];
for(int i = 1; i < n; i++){
for(int j = i; j >= 0; j --){
memo[i] = max(memo[i], nums[j] + (j-2 >= 0? memo[j-2]: 0));
}
}
return memo[n-1];
}
};
аналогичная проблема
- leetcode 213
- leetcode 337
- leetcode 309
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут лайкнуть / подписаться, ваша поддержка - самая большая поддержка для меня.
личный блогТоматная технология мелкоячеистаяиДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт в WeChat: Tomato Technology Stack.