个人网站域名申请,个人养老金怎么缴纳,北京百度seo公司,做网站现在好弄么前言#xff1a;对于动态规划#xff1a;该算法思维是在dfs基础上演化发展来的#xff0c;所以我不想讲的是看到一个题怎样直接用动态规划来解决#xff0c;而是说先用dfs搜索#xff0c;一步步优化#xff0c;这个过程叫做动态规划。#xff08;该文章教你怎样一步步的…前言对于动态规划该算法思维是在dfs基础上演化发展来的所以我不想讲的是看到一个题怎样直接用动态规划来解决而是说先用dfs搜索一步步优化这个过程叫做动态规划。该文章教你怎样一步步的解决这类题 目录
一、动态规划入门
二、跳台阶问题---来自AcWing
1.用暴力搜索dfs来解
2.记忆化搜索实现
3.递推实现
二、大盗阿福---来自AcWing
1.用dfs暴力搜索
2.记忆化搜索
3.递推实现
四、数字三角形---来自洛谷
1.用暴力搜索dfs
2.用记忆化搜索
3.递推dp 一、动态规划入门 动态规划就是给定一个问题我们将它拆解为一个个子问题直到子问题可以直接解决然后把子问题的答案保存起来以减少重复计算再根据子问题答案反推得出原问题的一种方法 动态规划入门思路dfs暴力---记忆化搜索---递推DP 下面正式开始讲解还是在题中带大家慢慢理解动态规划的思维
二、跳台阶问题---来自AcWing 一个楼梯共有n级台阶每次可以走一级或者两级问从第0级台阶走到第n级台阶一共有多少种方案。 输入格式 共一行包含一个整数n 输出格式 共一行包含一个整数表示方案数 数据范围 1n15 输入样例 5 输出样例 8 1.用暴力搜索dfs来解
这个题大部分同学都应该见过最初我们用递归来解决这道题其实本质上也是dfs暴力搜索
#includeiostream
#includealgorithm
using namespace std;
int n;
int fib(int x)
{if (x 1)return 1;else if (x 2)return 2;else return fib(x - 1) fib(x - 2);
}
int main(void)
{cin n;int res fib(n);cout res endl;return 0;
} 这时我们会发现当n41时时间就快到了1s所以要想办法去优化代码
2.记忆化搜索实现
这里我拿n5为例来画一下搜索树然后分析一下怎么优化 如果是用一个数组来存储一下的话直接就省去了这棵大树的右分支因为左分支中的3已经搜索过了当以后遇到别的题或者n更大时这棵树的左右分支也会很大所以省去的搜索也就更多。
#includeiostream
#includealgorithm
using namespace std;
int arr[100];
int n;
int fib(int x)
{if(arr[x])return arr[x];int sum0;if (x 1) sum1;else if (x 2) sum2;else sumfib(x-1)fib(x-2);arr[x]sum;return sum;
}
int main(void)
{scanf(%d,n);int res fib(n);printf(%d\n,res);return 0;
} 直接将900多毫秒优化到了2毫秒。
3.递推实现 递归的过程“归”的过程才是产生答案的过程 “递”的过程是分解子问题的过程把大问题分解为子问题 “递”自顶向下 “归”自底向上 而我们自底向上一步步推出答案的过程-----就是递推 好接下来就用递推的方式进行编程
#includeiostream
#includealgorithm
using namespace std;
int F[100];
int n;
int main(void)
{scanf(%d,n);F[1]1,F[2]2;for(int i3;in;i){F[i]F[i-2]F[i-1];//这个递推公式也就是dfs的状态转移公式}printf(%d\n,F[n]);return 0;
}
总结 跳台阶这道题我们就是这样做的 最暴力的dfs---记忆化搜索---递推dp 记忆化搜索暴力bfs记录答案 递推的公式dfs向下递归的公式 递推数组的初始值递归的边界 二、大盗阿福---来自AcWing 阿福是一名经验丰富的大盗。趁着月黑风高阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺每家店中都有一些现金。阿福事先调查得知只有当他同时洗劫了两家相邻的店铺时街上的报警系统才会启动然后警察就会蜂拥而至。 作为一向谨慎作案的大盗阿福不愿意冒着被警察追捕的风险行窃。 他想知道在不惊动警察的情况下他今晚最多可以得到多少现金? 输入格式: 输入的第一行是一个整数 T表示一共有 T 组数据。接下来的每组数据第一行是一个整数 N 表示一共有 N 家店铺,第二行是 N 个被空格分开的正整数表示每一家店铺中的现金数量每家店铺中的现金数量均不超过1000。 输出格式: 对于每组数据输出一行 该行包含一个整数表示阿福在不惊动警察的情况下可以得到的现金 范围 1T50 1N1e5 输入样例 2 3 1 8 2 4 10 7 6 14 输出样例 8 24 1.用dfs暴力搜索
先画搜索树这道题是选和不选问题 #includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
int arr[N];
int n, t;
int res 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (x n)return 0;else return max(dfs(x 1), dfs(x 2) arr[x]);
}
int main(void)
{cin t;while (t--){cin n;for (int i 1; i n; i)scanf_s(%d, arr[i]);int res dfs(1);}return 0;
} 放到官网提交一下答案发现时间超时因为dfs的时间复杂度是2的n次方超时是理所当然的事还是要想办法优化
2.记忆化搜索 要想实现记忆化搜索的话那么dfs的参数就需要尽可能的少不应该把没有影响到边界的参数放进来 #includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
int arr[N];
int mem[N];
int n, t;
int res 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum 0;if (x n) sum 0;else sum max(dfs(x 1), dfs(x 2) arr[x]);mem[x] sum;return sum;
}
int main(void)
{cin t;while (t--){cin n;for (int i 1; i n; i)scanf_s(%d, arr[i]);memset(mem, 0, sizeof mem);int res dfs(1);}return 0;
}
跟跳台阶一样的套路创建一个数组存放数据。
3.递推实现
前面也说过了递推的过程就是递归的“归”由搜索树的最底层开始向上推并且递推的公式就是向下递归的公式.
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
int arr[N];
//int mem[N];
int f[N];
int n, t;
int res 0;
#if 0
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum 0;if (x n) sum 0;else sum max(dfs(x 1), dfs(x 2) arr[x]);mem[x] sum;return sum;
}
#endif
int main(void)
{cin t;while (t--){cin n;for (int i 1; i n; i)scanf_s(%d, arr[i]);//memset(mem, 0, sizeof mem);memset(f, 0, sizeof f);for (int i n; i 0; i--){f[i] max(f[i 1], f[i 2] arr[i]);}//int res dfs(1);}return 0;
}
四、数字三角形---来自洛谷 还是一样的套路三种方法解决问题我希望大家先自己去尝试用这三种方法动手打一下代码哪里有不明白的直接看代码再自己理解一下编程还是自己去上手才能看出来明白还是不明白
1.用暴力搜索dfs
#includeiostream
#includealgorithm
using namespace std;
const int N 1005;
int arr[N][N];
int n;
int dfs(int x, int y)
{if (x n || y n)return 0;else return max(dfs(x 1, y) arr[x][y], dfs(x 1, y 1) arr[x][y]);
}
int main(void)
{cin n;for (int i 1; i n; i){for (int j 1; j i; j){cin arr[i][j];}}int res dfs(1, 1);cout res endl;return 0;
}
2.用记忆化搜索
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 1005;
int arr[N][N];
int mem[N][N];
int n;
int dfs(int x, int y)
{if(mem[x][y])return mem[x][y];int sum0;if (x n || y n) sum 0;else sum max(dfs(x 1, y) arr[x][y], dfs(x 1, y 1) arr[x][y]);mem[x][y]sum;return sum;
}
int main(void)
{cin n;for (int i 1; i n; i){for (int j 1; j i; j){cin arr[i][j];}}memset(mem,0,sizeof mem);int res dfs(1, 1);cout res endl;return 0;
}
3.递推dp
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 1005;
int arr[N][N];
int f[N][N];
int n;
int main(void)
{cin n;for (int i 1; i n; i){for (int j 1; j i; j){cin arr[i][j];}}for (int i n; i 1; i--){for (int j 1; j i; j){f[i][j] max(f[i 1][j] arr[i][j], f[i 1] [j 1] arr[i][j]);}}cout f[1][1] endl;return 0;
} 最后希望读完这篇文章的你对动态规划有了更深入的了解
