文章目录
- 一、简介
- 二、举个栗子
- 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;
else
return 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;
else
f[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;
}
参考资料
[1]https://leetcode.com/problems/minimum-path-sum/description/
[2]https://www.youtube.com/watch?v=OQ5jsbhAv_M
