咸阳网站网站建设,网站建设要多少钱品牌,甘肃省作风建设年活动有网站,个人如何做免费网站前言
本文以一道常见的算法面试题开篇#xff0c;引入动态规划的基础概念#xff0c; 介绍其思考过程。
正文
一、常见的一道算法面试题——上台阶
有一个楼梯总共n个台阶#xff0c;只能往上走#xff0c;每次只能上1个、2个台阶#xff0c;总共有多少种走法。
解决…前言
本文以一道常见的算法面试题开篇引入动态规划的基础概念 介绍其思考过程。
正文
一、常见的一道算法面试题——上台阶
有一个楼梯总共n个台阶只能往上走每次只能上1个、2个台阶总共有多少种走法。
解决方案
1、排列组合
枚举2的个数再枚举2具体放的位置
计算复杂容易遗漏。
2、动态规划
dp[n] 表示n个台阶的走法那么有
dp[n]dp[n-1]dp[n-2]
思路清晰代码简单。
二、动态规划基础概念
1、动态规划
动态规划Dynamic Programming指的是解最优化问题的一种方法。
2、最优子结构性质
问题的最优解可以分解为若干子问题且子问题的解也是最优的
以上台阶为例到第i层的最多走法可以分解为第i-1层和第i-2层的走法之和且第i-1层和第i-2层的走法也是最多的
3、 无后效性
现阶段的决策不会影响未来的决策
以上台阶为例走到第i-2层的最多走法不会因为增加第i-1层而改变
三、动态规划思考过程
动态规划的思考过程可以总结为大事化小小事化了。
大事化小
一个较大的问题通过找到与子问题的重叠把复杂的问题划分为多个小问题也称为状态转移
小事化了
小问题的解决通常是通过初始化直接计算结果得到
具体的步骤
1、将大问题分解为子问题
2、确定状态表示
3、确定状态转移
4、考虑初始状态和边界情况
四、另一个经典的例子——数塔
有如图所示的数塔要求从顶层走到底层若每一步只能走到相邻的结点则经过的结点的数字之和最大是多少 解决思路
1、大事化小。要到达第i层先要到达第i-1层。并且第i层的第j个节点只能由i-1层的第j个和第j-1个节点到达。
我们用dp[i][j]表示走到第i层第j个位置的数字最大和。
那么有dp[i][j]max(dp[i-1][j], dp[i-1][j-1]) a[i][j];
2、小事化了。第1层的第1个节点初始值为dp[1][1]a[1][1]。a[x][y]表示第x层第y个的值
五、数塔例子的变形——收集苹果
平面上有N*M个格子每个格子中放着一定数量的苹果。
你从左上角的格子开始每一步只能向下走或是向右走每次走到一个格子上就把格子里的苹果收集起来。这样下去你最多能收集到多少个苹果。
解决思路
1、只能向右走或者向下走要到达第i行第j列的格子的时候可以由第i-1行第j列或者第i行第j-1列到达我们用dp[i][j]表示走到第i行第j列的最多苹果数那么有
dp[i][j]max(dp[i-1][j], dp[i][j-1]) a[i][j];
2、第1行第1列初始值为dp[1][1]a[1][1]注意事项是边界条件的处理。
六、动态规划经典——01背包问题
给定n件物品和一个容量为m的背包每件物品都会消耗背包的一定容积c[i]并带来一定价值v[i]要求如何选取装入背包中的物品使得背包内的物品价值最大。
解决思路
把n件物品放入背包可以分解为“将前i件物品放入容量为m的背包中”问题。
若只考虑第i件物品的选择那么问题可以分为两种情况
1、如果不放第i件物品问题就转化为“前i-1件物品放入容量为v的背包中”
2、如果放第i件物品问题就转化为“前i-1件物品放入剩下的容量为m-c[i]的背包中”
我们用f[i][j]表示前i个物品放入容量为j的背包的最大价值上面的两种情况可以表示为
f[i][j] max(f[i-1][j], f[i-1][j-c[i]]v[i]);
初始化条件memset(dp, 0, sizeof(dp));和dp[1][c[1]]v[1]。
最后遍历f[n][1~m]可以得到最大值。
总结
如果还不能完全理解01背包那么还需要再仔细理解最优子结构、状态表示和状态转移。
算法能扩展思考方向完善思维能力。学会“上台阶”、“数塔”、“01背包”这三个题目能解决算法面试的动态规划部分。
参考及引用
程序员算法基础——动态规划
