动态规划初探-递推
 visitors

概述

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构(英语:Optimal substructure)性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。

动态规划在查找有很多重叠子问题的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,他们的结构都逐渐计算并保存,从简单的问题直到整个问题被解决。因此,动态规划保存递归时候的结果,因而不会再解决同样的问题时花费时间。动态规划只能用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

以上描述来自维基百科

骨牌铺方格

题目描述

在2*n的长方形方格中,用一个1x2的骨牌铺满方格,输入n,输出铺满方格的方案总数。

问题分析

我们用f[i]表示2xi的方格铺满骨牌的方案数,那么考虑到第i列,要么竖着放置一个骨牌;要么连同i-1列,横着放置两个骨牌,如下图所示。由于骨牌的长度为1x2,所以在第i列放置的骨牌无法影响到第i-2列。很显然,图中两块黑色的部分分别表示f[i-1]f[i-2],所以可以得到递推公式f[i]=f[i-1]+f[i-2],并且边界条件为f[0]=f[1]=1

问题升级I

有两种形状的瓷砖:一种是2x1的多米诺形,另一种是形如”L”的托米洛形。两种形状都可以旋转。给定N的值,有多少种方法可以平铺2xN的面板?

题目链接:https://leetcode.com/problems/domino-and-tromino-tiling/

如上图可得到递归公式为:

1
2
3
4
5
dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]

问题升级II

在3*n的长方形方格中,用一个1x2的骨牌铺满方格,输入n,输出铺满方格的方案总数。

首先我们可以确定当n等于奇数的时候,方案数一定为0。所以如果用fi表示3xi的方格铺满骨牌的方案,f[i]的方案数不可能由f[i-1]递推而来。那么可以猜想f[i]f[i-2]一定是有关系的,如下图所示,我们把第i列和第i-1列用1x2的骨牌填满后,轻易转化成了f[i-2]的问题,那是不是代表f[i]=3*f[i-2]呢?

仔细想才发现不对,我们少考虑了如下的情况,这些情况无法用上图的情况表示,发现和f[i-4]也有关系,但是还是漏掉了一些情况。

上面的问题说明我们在设计状态的时候的思维定式,当一维的状态已经无法满足我们的需求时,我们可以试着增加一维,用二维来表示状态,用f[i][j]表示3xi+j个多余块的摆放方案数,如下图所示:

转化成二维后,我们可以写出如下三种情况的递推式:

1
2
3
f[i][0]=f[i-2][0]+f[i-1][1]+f[i-2][2]
f[i][1]=f[i-1][2]
f[i][2]=f[i][0]+f[i-1][1]

边界条件f[0][0]=f[1][1]=f[0][2]=1