C++ 动态规划

文章目录

一、简介
二、举个栗子
- 2.1斐波那契数列
- 2.2最短路径（DFS）
参考资料

一、简介

感觉动态规划非常的实用，因此这里整理一下相关资料。动态规划（Dynamic Programming）：简称 DP，是一种优化算法，它特别适合去优化一些问题，如最短路径等（设计到最小化以及最大化的问题，都可以考虑该方法），它具有通用性。通俗来讲，可以将其视为一种穷举搜索算法，但是不同于穷举算法，它会避免许多无意义的重复操作，从而节省时间，因此也可以将其描述为“谨慎的蛮力”。

tips：动态规划一词最早由理查德·贝尔曼于 1957 年在其著作《动态规划（Dynamic Programming）》一书中提出。这里的 Programming 并不是编程的意思，而是指一种[表格处理方法]，即将每一步计算的结果存储在表格中，供随后的计算查询使用，据说是最早用于处理火车的规划问题。还有另一个原因就是，本来贝尔曼想以“研究（research）”之类的词进行命名，但是国防部的官员对“研究”一词极为恐惧和厌恶，因此就采用了Programming一词（折中方案）。

DP问题存在这样一个通用的框架：

记忆化处理（记录每次计算的结果）。
找出子问题（它往往与其他问题有所关联，其结果可以被重复使用，注：子问题的依赖关系应是非循环的）。
穷举所有可能的结果（也就是猜，如最短路径），有的算法不需要这一步处理。

因此DP问题也可以被描述为一个：递归+记忆化处理+猜（可能存在）的过程，它的计算时间是子问题数量*每个子问题所花费的时间。当然一句话的概况往往是有形而无用的，还是需要多结合实际情况去感受，因此可以以一些例子来进一步学习。

二、举个栗子

2.1斐波那契数列

1，1，2，3，5，8，13，21，34，55，89……

首先我们可以写一个原始的版本（递归）：

#include <iostream>
#include <unordered_map>int f(int n)
{if (n < 2)return 1;elsereturn f(n - 1) + f(n - 2);
}int main(int argc, char* argv[])
{// -------------------------动态规划---------------------------// 斐波那契数列int n = 7;		//以0为起始std::cout << "计算结果：" << f(n) << std::endl;std::cout << "计算结束!" << std::endl;return 0;
}

在这里插入图片描述

不过由于上述的版本存在很多重复的计算，比如计算f(n)是会计算f(n-1)与f(n-2)，而计算f(n-1)时则又会重新计算f(n-2)，以此类推当n很大时，上面程序的复杂度会以指数级增长，因此这里就可以利用简单的动态规划思路来加速计算过程（有时候追本溯源还是很有用的，我们只需要像创始人那样创建一个表即可）。

#include <iostream>
#include <unordered_map>//创建一个表用于记录
std::unordered_map<int, int> fm;int f(int n)
{if (fm.find(n) != fm.end())return fm[n];if (n < 2){fm[n] = 1;return 1;}else{fm[n] = f(n - 1) + f(n - 2);return fm[n];}
}int main(int argc, char* argv[])
{// -------------------------动态规划---------------------------// 斐波那契数列int n = 7;		//以0为起始std::cout << "计算结果：" << f(n) << std::endl;std::cout << "计算结束!" << std::endl;return 0;
}

在这里插入图片描述

不过上述的代码仍然不够完美，这是因为我们是自顶向下的过程，这个过程中我们依赖于递归这种方式，存在许多函数调用的过程，因此我们可以继续简化：

#include <iostream>
#include <unordered_map>int main(int argc, char* argv[])
{// -------------------------动态规划---------------------------// 斐波那契数列int n = 7;		//以0为起始std::unordered_map<int, int> f;for (int i = 0; i <= n; ++i){if (i < 2)f[i] = 1;elsef[i] = f[i - 1] + f[i - 2];}std::cout << "计算结果：" << f[n] << std::endl;std::cout << "计算结束!" << std::endl;return 0;
}

在这里插入图片描述

2.2最短路径（DFS）

假设从一个棋盘的左上角走到右下角，求取最大路径之和，思路其实和上面相同，只是操作上略有不同：

// 标准文件
#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include <fstream>
#include <stack>#define COMP >static int maxPathSum(std::vector<std::vector<int>>& grid) {int b = grid[0].size();int c = grid.size();std::vector<std::vector<float>> dp(c);std::vector<std::vector<std::pair<int, int>>> coords(c);for (int i = 0; i < dp.size(); ++i){dp[i].resize(b);coords[i].resize(b);}//int dp[c][b];std::cout << "行数：" << c << ",列数：" << b << std::endl;dp[0][0] = grid[0][0];coords[0][0] = std::make_pair(-1, -1);//初始化行for (int i = 1; i < c; i++){dp[i][0] = dp[i - 1][0] + grid[i][0];coords[i][0] = std::make_pair(i - 1, 0);}//初始化列for (int j = 1; j < b; j++){dp[0][j] = dp[0][j - 1] + grid[0][j];coords[0][j] = std::make_pair(0, j - 1);}for (int i = 1; i < c; i++){for (int j = 1; j < b; j++){if (dp[i - 1][j] COMP dp[i][j - 1]&& dp[i - 1][j] COMP dp[i - 1][j - 1]){coords[i][j] = std::make_pair(i - 1, j);dp[i][j] = dp[i - 1][j] + grid[i][j];}else if (dp[i - 1][j - 1] COMP dp[i][j - 1]&& dp[i - 1][j - 1] COMP dp[i - 1][j]){coords[i][j] = std::make_pair(i - 1, j - 1);dp[i][j] = dp[i - 1][j - 1] + grid[i][j];}else{coords[i][j] = std::make_pair(i, j - 1);dp[i][j] = dp[i][j - 1] + grid[i][j];}//dp[i][j] = std::max(dp[i - 1][j],//    std::max(dp[i - 1][j - 1], dp[i][j - 1]))//    + grid[i][j];}}//距离矩阵std::cout << "距离矩阵：" << std::endl;for (int i = 0; i < dp.size(); ++i){std::vector<float> row = dp[i];for (int j = 0; j < row.size(); ++j){std::cout << row[j] << " ";}std::cout << std::endl;}//索引矩阵std::cout << "索引矩阵：" << std::endl;for (int i = 0; i < coords.size(); ++i){std::vector<std::pair<int, int>> row = coords[i];for (int j = 0; j < row.size(); ++j){std::cout << "(" << row[j].first << "," << row[j].second << ")" << " ";}std::cout << std::endl;}std::cout << "输出路径：" << std::endl;std::deque<std::pair<int, int>> queue;queue.push_front(std::make_pair(c - 1, b - 1));std::pair<int, int> pos = coords[c - 1][b - 1];while (pos.first > -1){queue.push_front(pos);pos = coords[pos.first][pos.second];}for (int i = 0; i < queue.size() - 1; ++i){std::cout << "(" << queue[i].first << "," << queue[i].second << ")" << "->";}std::cout << "(" << queue[queue.size() - 1].first << ","<< queue[queue.size() - 1].second << ")" << "\n";return dp[grid.size() - 1][grid[0].size() - 1];
}int main(int argc, char** argv)
{// ---------------------输入数据---------------------std::vector<std::vector<int>> data ={{1,3,1,1},{1,5,1,1},{4,2,1,1}};// ---------------------动态规划---------------------std::cout << "最大距离：" << maxPathSum(data) << std::endl;return 0;
}