「手撕算法」锁定大厂看这就可

在计数问题中，为了保证计数的准确程度，通常会保证两个问题，第一个问题是没有重复，第二个问题是没有遗漏。这两个问题相对来说，第二点比较容易做到。比如对某地区进行爆炸式轰炸，为了保证炸的覆盖面，足够多的炸弹即可，但是如果保障一块土地只能炸一次就比较难搞了。那么容斥原理就是解决这个问题

容斥原理是什么?

先不考虑重叠的情况，先将所有对象数目计算出来，然后将重复计算的排斥出去，是的，计算的结果不仅不遗漏也不重复。简单的说就是在计算的过程中，如果加多了就减去多的部分，如果减多了就加回来一部分，直到不多不少。

我们看一个兔子繁殖问题

假设有一片草原上，莫名其妙来了一只外星兔子，这种外星兔子呢，第一个月的时候是幼体，第二个月成长为成体，从第三个月开始，成体兔子每个月都会产生出一只克隆体的幼体兔子，而且这种兔子不会衰老，一旦成体以后，就会一直生下去。按照这种情况，请你计算出第 n 个月，草原上有多

少只兔子?

此时给出前面6个月的情况

六个月兔子情况

从上图我们可以发现，从第一个月到第六个月，草原上的兔子数量分别为1,1,2,3,5,8

第六个月共有8只兔子，其中包含5只成兔，3只幼兔，为什么是5只成兔，因为第六个月的兔子数量等于第五个月的兔子总数，六个月的3只幼兔是等于第四个月的兔子数量

后三个月情况

结论就比较清晰了：从第三个月开始，第n个月的兔子数量等于该月的成兔数量与幼兔数量之和，也就是等于第n-1个月的兔子数量与第n-2兔子数量之和。这种根据前面的数量来推后面的数量的情况叫做递推，那么递推算法套路通常是怎么样呢

确定递推的状态，多画图前面几步 推导递推公式 程序的编写

我们根据三步走的方式来阐释解决兔子的这个问题

f(n)表示n个月兔子的数量 递推公式(第一个月合第二个月兔子的数量为1，到了第三个月即等于前面两个月之和)

递推公式

案例2 凑钱币问题

用 1 元、2 元、5 元、10 元、20 元、50 元和 100

元凑成 1000 元钱，总共有多少种方案

确定递推状态，需要分析自变量与因变量，自变量两个分别为币种种类和拼凑的钱币数量，因变量1个为方案总数，因此我们的状态定义为f(i,j)，i种钱币，拼凑j元钱的方案总数。比如f [3][10]即使用三种钱币，凑出10元的方案总数 假设我们不使用第三种钱币，那么此时等价于使用前两种钱币拼凑10元钱的方案总数，即f[2][10]。如果使用至少1张5块钱，那么我们在这些方案中去掉一张5元钱，剩下的方案数为f[3][5]，所以此时的递推公式为f[3][10] = f[2][10] + f[3][5]。这只是一般情况，假设我们没有使用第i种钱币，拼凑j元的方案为f(i-1,j)，代表使用前i-1种钱币的方案总数。剩下的使用了第i中钱币，由于都存在第i钱币1张，假设第i种钱币的面额为val[i]，那么此时我们的前i种钱币，凑j-val[i]的钱数，此时方案总数为f(i,j-val[i]);所以公式为f(i,j)=f(i-1,j)+f(i,j-val[i])

推理

7 动态规划

动态规划通常简称DP(dynamic programming)，如果按照问题类型来划分，将分为线性DP、区间DP，数位DP等等，每当说到动态规划就会想最优子结构，重叠子问题等等，这些词汇苦涩难懂，不要慌，再难的问题也是建立在基础问题上，逐步拆分，这也是动态规划的思想，相信通过下面动态规划四步走的方式，加上习题的练习，一定会让你对动态规划有个新的理解。

四个步骤分为：状态定义，状态转移方程，正确性的证明和实现

状态定义

其实上面说递推的时候就已经有所涉及状态定义，通常在推导的过程中，如果感觉推不下去了，很有可能就是我们的状态定义出现了问题。

第一个状态：dp[i][j]代表从起始点到(I,j)路径的最大值

第二个状态：dp[i][j]代表从底边的某个点出发，到达(i,j)路径的最大值

状态转移方程

上面的两种状态定义对应这里两个转移方向。

状态转移过程

如上图所示，我们想要求得dp[i][j]，需要知道dp|[i-1]|[j-1]和dp[i-1][j]的值。因为只有(i - 1, j - 1) 和 (i - 1, j) 这两个点，才能能走到 (i, j)此时的状态转移方程为

第一种状态转移方程dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j]

第二册中状态转移方程dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]

从这里可以知道我们的状态定义不一样，我们的转移方程就很不一样吧

正确性证明

数学归纳法通常采用三步走的方式，常用的正确性证明方法为数学归纳法。

第一步，第一个阶段所有dp值可以轻松获得，也就是初始化dp[1][1]，等于val[1][1]

第二步，假设如果第i-1阶段的所有状态值都正确得到，那么根据状态方程dp[i][j]=max(dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j] 来说，此时就可以计算得到第i阶段中的素有状态值

第三步：得出结论，所有的状态值计算正确

我们继续分析动态规划问题中的0/1背包问题，通常分为三类，0/1背包问题，完全背包问题和多重背包问题。

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!