文档介绍：动态规划
Dynamic Programming
先来一题
说,有个人从上往下走,每次只能往左下方走或者右下方走,选一条路径使得它权值之和最大,问最大值为多少?
分析
对于每一个节点,保存从起点走到该节点的权值之和的最大值。每个节点查找完找出最后一行的最大值即可。
假设该节点为n行m列,则有
dp[n][m]=
Max{dp[n-1][m-1],dp[n-1][m]}+a[n][m]
想想
如果我要求出这条路径怎么办??
这道题和算杨辉三角有什么区别??
根据上一问得出的结论,想想动态规划和递推有什么差别?
分析
对于一个节点的值,是如何得到的?
无非是由dp[n-1][m-1]和dp[n-1][m]的最大值加上a[n][m]得到的,那么可以将dp[n][m]-a[n][m],看这个值等于dp[n-1][m-1]还是dp[n-1][m]。就可以判断该点是从哪点走过来的。
想想,动态规划一般存在Max,Min的抉择,而并非直接由一个值得到下一个状态的值。
再来一题
如果拓展到矩形呢?
给定一个n*n的矩形,从(1,1)点走到(n,n)点,问怎么走使得权值之和最大??
例如
1 2 3
4 5 6
7 8 9
显然最大值为29.
和前一题一样
一样的,对于每个节点都从左边和上边来……所以最后只要看最后一点的值即可
很水是吧?
那么问问,如果求对4取余的最大值呢?
求乘积最大值呢?
求乘积末尾0的个数的最小值呢?
分析
对4取余的话,那么可以将数组加一维
dp[n][m][k]表示走到n行m列是否存在对4取余余数为k的,如果存在就是1,不存在就是0.
dp[n][m][k]=
Max{dp[n-1][m][(k+4-a[n][m]%4])%4,
dp[n][m-1][(k+4-a[n][m]%4]]}
分析
乘积最大,不也一样么……orz
如果要求乘积最大的末尾0的个数最少,那么先想想,末尾0是怎么来的
无非是有个因子2和一个因子5么……
那么做两遍动态规划,一遍是找出因子2最少的个数,一遍是找出因子5最少的个数,那么末尾0的最少个数就是Min{因子2的个数,因子5的个数}。