是动态规划类型相关的题目动态规划类的题目在笔试和面试中是考察非常高频的一类要想掌握这一类的题目就需要在掌握正确的学习方法的前提下做大量的练习下面为大家介绍几道动态规划中比较经典的题目每一道题目都有非常详细的思路实现看完相信大家一定会有收获的

1.动态规划概念

Programming简称DP如果某⼀问题有很多重叠⼦问题使⽤动态规划是最有效的动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的

2.动态规划解题步骤

找问题的最好⽅式就是把dp数组打印出来看看究竟是不是按照⾃⼰思路推导的做动规的题⽬写代码之前⼀定要把状态转移在dp数组的上具体情况模拟⼀遍⼼中有数确定最后推出的是想要的结果。

然后再写代码如果代码没通过就打印dp数组看看是不是和⾃⼰预先推导的哪⾥不⼀样。

如果打印出来和⾃⼰预先模拟推导是⼀样的那么就是⾃⼰的递归公式、初始化或者遍历顺序有问题了。

如果和⾃⼰预先模拟推导的不⼀样那么就是代码实现细节有问题。

4.动态规划经典题目

如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是⼀致的。

class

爬到第⼀层楼梯有⼀种⽅法爬到⼆层楼梯有两种⽅法。

那么第⼀层楼梯再跨两步就到第三层

动规五部曲

。

在推导dp[i]的时候⼀定要时刻想着dp[i]的定义否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性3.

dp数组如何初始化

那么i为0dp[i]应该是多少呢这个可以有很多解释但都基本是直接奔着答案去解释的。

例如强⾏安慰⾃⼰爬到第0层也有⼀种⽅法什么都不做也就是⼀种⽅法即dp[0]

那还这么理解呢我就认为跑到第0层⽅法就是0啊⼀步只能⾛⼀个台阶或者两个台阶然⽽楼层是0直接站楼顶上了就是不⽤⽅法dp[0]就应该是0.

其实这么争论下去没有意义⼤部分解释说dp[0]应该为1的理由其实是因为dp[0]1的话在递推的过程中i从2开始遍历本题就能过然后就往结果上靠去解释dp[0]

需要注意的是题⽬中说了n是⼀个正整数题⽬根本就没说n有为0的情况。

我相信dp[1]

打印出来看看究竟是不是和⾃⼰推导的⼀样。

此时⼤家应该发现了这不就是斐波那契数列么唯⼀的区别是没有讨论dp[0]应该是什么因为dp[0]在本题没有意义

class

个台阶向上爬需要支付的费用。

一旦你支付此费用即可选择向上爬一个或者两个台阶。

或下标为

题目描述中说可以选择向上一次爬一个台阶或者一次爬两个台阶所以到达第i阶台阶可以通过第i-1阶台阶到达或者是通过第i-1阶台阶到达然后在根据题目描述求的是达到顶楼所需要花费的最小体力所以递推公式可以推导出

dp[i]

的台阶开始爬楼梯也就是说到下标为0的台阶和到下标为1的台阶是不需要花费体力的所以应该初始化为

dp[0]

minCostClimbingStairs(vectorint

cost)

{vectorintdp(cost.size()1);dp[0]

0;dp[1]

min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return

dp[cost.size()];}

机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角在下图中标记为

“Finish”

根据题目中的描述机器人每次只能向下或者向右移动一步所以到达dp[i][j]的路径总数是到达dp[i-1][j]的路径总数加上到达dp[i][j-1]的路径总数之和所以递推公式应该为dp[i][j]

dp[i-1][j]

1]dp[i][j]都是从其上⽅和左⽅推导⽽来那么从左到右⼀层⼀层遍历就可以了。

举例推导dp数组

{vectorvectorintdp;dp.resize(m);for

(int

机器人每次只能向下或者向右移动一步。

机器人试图达到网格的右下角在下图中标记为

现在考虑网格中有障碍物。

那么从左上角到右下角将会有多少条不同的路径

输入obstacleGrid

0)的路径只有⼀条所以dp[i][0]⼀定为1dp[0][j]也同理。

但如果(i,

这条边有了障碍之后障碍之后包括障碍都是⾛不到的位置了所以障碍之后的dp[i][0]应该还是初始值0。

下标(0,

注意代码⾥for循环的终⽌条件⼀旦遇到obstacleGrid[i][0]

1的情况就停⽌dp[i][0]的赋值1的操作dp[0][j]同理

确定遍历顺序

中可以看出⼀定是从左到右⼀层⼀层遍历这样保证推导dp[i][j]的时候dp[i

1][j]

uniquePathsWithObstacles(vectorvectorint

obstacleGrid)

obstacleGrid[0].size();vectorvectorintdp;dp.resize(m);for(int

dp.size();

i){dp[i].resize(n,0);}//初始化第一行for(int

1)break;dp[0][i]

dp[i]最⼤乘积是怎么得到的呢其实可以从1遍历j然后有两种渠道得到dp[i].

dp[i

1的初始化但解释⽐较牵强主要还是因为这么初始化可以把题⽬过了。

dp[1]

1从dp[i]的定义来说拆分数字2得到的最⼤乘积是1这个没有任何异议

确定遍历顺序

j]再有dp[i]。

枚举j的时候是从1开始的。

i是从3开始这样dp[i

for

这道题⽬描述很简短但估计⼤部分同学看完都是懵懵的状态这得怎么统计呢面对这道题我们应该画画图看看有没有什么规律

当1为头结点的时候其右⼦树有两个节点看这两个节点的布局是不是和

可能有同学问了这布局不⼀样啊节点数值都不⼀样。

别忘了我们就是求不同树的数量并不⽤把搜索树都列出来所以不⽤关⼼其具体数值的差异

当3为头结点的时候其左⼦树有两个节点看这两个节点的布局是不是和n为2的时候两棵树的布局也是⼀样的啊

当2位头结点的时候其左右⼦树都只有⼀个节点布局是不是和n为1的时候只有⼀棵树的布局也是⼀样的啊

发现到这⾥其实我们就找到的重叠⼦问题了其实也就是发现可以通过dp[1]

dp[2]

此时我们已经找到的递推关系了那么可以⽤动规五部曲在系统分析⼀遍。

确定dp数组dp

初始化只需要初始化dp[0]就可以了推导的基础都是dp[0]。

那么dp[0]应该是多少呢

从定义上来讲空节点也是⼀颗⼆叉树也是⼀颗⼆叉搜索树这是可以说得通的。

确定遍历顺序