动态规划基本概念

Posted on

我们先看一个问题：

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

这个问题暴力求解是可以，但是不够美。我们从动态规划的角度来理解下。

动态规划（ DP ）是一种分阶段求解决策问题的数学思想。总结起来就是一句话，大事化小，小事化了。

问题建模

假如用户最后只差一步就可以走完整个楼梯，根据条件我们知道，这个时候会有两种情况出现

  • 用户在还差一级台阶，9 -> 10
  • 用户还差两级台阶，8 -> 10

意味着我们只要知道了前九级和前八级分别需要多少种走法，即可知道走完十级需要多少种走法。

现在假设$F(n)$表示到第$n$个台阶一共的走法，即：

同理可得，假设用户还差一步可以走到第九级，那么：
…
到最后：

当只有1级台阶和2级台阶时走法很明显，即$ F(1) = 1,F(2) = 2$。现在我们已经成功地把一个复杂地问题简单化啦，这就是动态规划。

最后我们可以得到归纳出以下公式$F$：

动态规划中包含三个重要的概念，最优子结构、边界、状态转移公式

  • 上面问题中，我们知道了$F(10) = F(9) + F(8)$，后两者就是前者的最优子结构。
  • $F(1)$和$F(2)$我们已经不需要简化，这个我们称之为边界。
  • $F$就是状态转移公式。

问题代码实现

使用递归的方法去做：

1
2
3
4
5
6
7
8
def calcWalkWays(n):

	if n == 1:
		return 1
	if n == 2:
		return 2
	else:
		return calcWalkWays(n-1) + calcWalkWays(n-2)

使用dp的方法去做：

1
2
3
4
5
6
def calcWalkWays(n):
	dp = [0 for k in range(n)]
	dp[0],dp[1] = 1,2
	for i in range(2,n):
		dp[i] = dp[i-1] + dp[i-2]
	return dp[-1]

两种方法都可以取得正确答案，但是第二种明显会快很多，这个可以自己去测试一下。