程序员小白常犯的错误及规避之道

7 动态规划

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

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

• 状态定义

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

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

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

• 状态转移方程

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

 

案例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])

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

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

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

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

（编辑：南通站长网）

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