基础理论
递归:
递:大问题分解子问题的过程 ; 归:产生答案
dp:只进行归;用已知的最底层的(递归的边界,搜索树的底),推出未知
一句话:
dp数组(不一定是数组,也可以是有限数间的来回递推)
递推关系:dfs向下递归的公式
dp数组初始化:递归的边界
动态规划题目的基础就是:回溯——记忆化——dp(一层比一层效率高)
例:
例题
打家劫舍
#include<iostream>
using namespace std;
#include<vector>
vector<int>nums = { 10,11,7,12 };
vector<int>memo(100, -1);
int dfs(int index) //暴力
{
if (index >= nums.size()) return 0;
return max( dfs(index + 2) + nums[index], dfs(index + 1) ); //这两个dfs分别代表选和不选,两种情况下的max
}
int mem(int index) //记忆化
{
if (memo[index] != -1) return memo[index]; //这个数下面的最大值我们已经记录了,直接返回即可
if (index >= nums.size()) return 0;
return memo[index]= max(mem(index + 2) + nums[index], mem(index + 1)); //记录当前下面子树最大值
}
int main()
{
cout << "暴力:"<< dfs(0) << endl << "记忆化:" << mem(0) << endl;
vector<int>dp(nums.size(), 0); //dp.1 dp[i]就是当前房屋的max
dp[0] = nums[0]; dp[1] = max(nums[0],nums[1]);
for (int i = 2; i < nums.size(); i++)
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); //画图,一定要画图,用: 10 11 7 12等试试看,会很通透
int a = nums[0], b = max(nums[0], nums[1]), c = 0; //dp.2
for (int i = 2; i < nums.size(); i++)
{
c = max(a + nums[i], b);
a = b;
b = c;
}
cout << "dp1:" << dp[nums.size() - 1] << endl;
cout << "dp2:" << b << endl;
return 0;
}
爬楼梯(斐波那契)
递推草稿&视频:动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili
#include<iostream>
using namespace std;
#include<vector>
#include<chrono>
vector<int>memo(100, -1);
int mem(int index) //记忆化(剪枝)
{
if (memo[index] != -1) return memo[index];
if (index == 1) return 1;
if (index == 2) return 2;
memo[index] = mem(index - 1) + mem(index - 2);
return memo[index];
}
int dfs(int index) //暴力
{
if (index == 1) return 1;
if (index == 2) return 2;
return dfs(index - 1) + dfs(index - 2);
}
int time(int(*k)(int),int n) //用时测试函数
{
auto start = std::chrono::steady_clock::now();
k(n);
auto end = std::chrono::steady_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}
int main()
{
int n; cin >> n;
cout << dfs(n) << endl << mem(n) << endl;
memo.clear(); memo.resize(100,-1);
cout <<"暴力用时:"<< time(dfs, n) << " " <<"记忆化用时:" << time(mem, n) << endl;
vector<int>dp(n, 0); //dp 当然也可以用三个变量来互相推
dp[0] = 1, dp[1] = 2;
for (int i = 2; i < n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n - 1] << endl;
return 0;
}