算法学习笔记（8.1）-动态规划入门

问题特性：

最优子结构：

代码示例：（动态规划最优子结构）

上述最小代价爬楼梯的运行过程：

代码示例：

无后效性：

解析：

具体过程图示如下：

具体的代码示例：

解析：

问题特性：

动态规划的基本是通过子问题分解来求解原问题的。但是通俗来说，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点也不同。

分治问题：递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解
动态规划：对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠的子问题。
回溯：在尝试和回退中穷举所有的可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题

实际上，动态规划常用来求解最优化问题，它不仅包含重叠子问题，还具有两大特性：最优子结构，无后效性。

最优子结构：

给定一个楼梯，你每步可以上1阶或者2阶，每一个楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组cost，其中cost[i]表示在第i个台阶需要付出的代价，cost[0]为地面（起始点）。

请计算最少需要付出多少代价才能到达顶部。

若第1，2，3阶的代价分别为1，10，1，则地面爬到第3阶的最小代价为2.

设dp[i]为爬到第i个台阶付出的代价，由于第i阶只能从i-1阶或者i-2阶走来，因此dp[i]只可能等于dp[i-1] + cost[i] 或者 dp[i-2] + cost[i]。为了尽可能减少代价，我们应该选择两者居中较小的那个：

dp[i] = min(dp[i-1],dp[i-2]) + cost[i]

这里就可以直接得出最优字结构的含义：原问题的最优解是从子问题的最优解构建而来。

但是对于爬楼梯的最优子结构，我们又该怎么理解呢，它的目标是求解方案数量，但是我们将其理解称为最大方案数量，虽然题目的含义一样，但是在这里出现了最优子结构的痕迹：第n阶方案最大数量=第n-1阶和第n-2阶最大方案数量和。

根据状态转移方程，以及初始状态dp[1] = cost[1]和dp[2] = cost[2]。

代码示例：（动态规划最优子结构）

# python 代码示例
def min_cost_climbing_stairs_dp(cost) :n = len(cost) - 1if n == 1 or n == 2 :return cost[n]dp = [0] * (n + 1)dp[1], dp[2] = cost[1], cost[2]for i in range(3, n + 1) :dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]return dp[n]

// c++ 代码示例
int minCostClimbingStairsDP(vector<int> &cost)
{int n = cost.size() - 1 ;if (n == 1 || n == 2){return cost[n] ;}vector<int> dp(n + 1) ;dp[1] = cost[1] ;dp[2] = cost[2] ;for (int i = 3; i <= n ; i++){dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] ;}return dp[n] ;
}

上述最小代价爬楼梯的运行过程：

将上述代码进行空间优化，将一维压缩至0维，空间复杂度由O(n)变为O(1)

代码示例：

# python 代码示例
def min_cost_climbing_stairs_dp_comp(cost) :n = len(cost) - 1if n == 1 or n == 2 :return cost[n]a, b = cost[1], cost[2]for i in range(3, n + 1) :a, b = b, min(a, b) + cost[i]return b

// c++ 代码示例
int minCostClimbingStairsDPComp(vector<int> &cost)
{int n = cost.size() - 1 ;if (n == 1 || n == 2){return cost[n] ;}int a = cost[1], b = cost[2] ;for (int i = 3 ; i <= n ; i++){int temp = b ;b = min(a, b) + cost[i] ;a = temp ;}return b ;
}

无后效性：

能够有效解决问题的重要特性之一，定义：给定一个确定的状态，它的未来发展只与当前的状态有关，而与过去经历的所有状态无关。

以爬楼梯进行相关理解，给定状态i，它会发展出状态i+1和状态i+2，分别对应跳1步和跳2步。在做出这两种选择时，无须考虑状态i之前的状态，它们对i的未来没有影响。

但是下面这种情况就不一样了：如题，给定一个共有n阶的楼梯，你每一步可以上1阶或者2阶，但是不能连续两次跳1阶，请问有多少种方案可以爬到楼顶？

如图所示：爬3阶的例子

解析：

如果上一轮跳1阶上来的，下一次跳动必须跳2阶。这就意味着，下一步的选择不能由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上一轮的楼梯的阶数）有关。

所以原来的状态转移方程dp[i] = dp[i-1] + dp[i-2]也因此失效，为了满足约束条件，我们不能直接将dp[i-1]直接放入到dp[i]中。

为此，我们需要扩展状态定义：状态[i,j]表示处在第i阶并且上一轮跳了j阶，其中j属于{1，2}。此状态定义有效地区分了上一轮跳了1阶还是2阶，我们可以根据判断当前状态从何而来。

当上一轮跳了1阶时，上上一轮只能选择跳2阶，即dp[i,1]只能从dp[i-1,2]转移过来
当上一轮跳了2阶时，上上一轮可选择跳1阶或者跳2阶，即dp[i,2]可以从dp[i-2,1]或dp[i-2,2]转移过来。

因此，在该定义下,dp[i,j]表示状态[i,j]对应的方案数。状态转移方程为：

dp[i,1] = dp[i-1,2]

dp[i,2] = dp[i-2,1] + dp[i-2,2]

具体过程图示如下：

最终，返回dp[n,1] + dp[n,2]即可，两者之和代表爬到第n阶的方案总数：

具体的代码示例：

# python 代码示例
def climbing_stairs_constraint_dp(n) :if n == 1 or n == 2 :return 1dp = [ [0] * 3 for _ in range(n + 1)]dp[1][1], dp[1][2] = 1, 0dp[2][1], dp[2][2] = 0, 1for i in range(3, n + 1) :dp[i][1] = dp[i - 1][2]dp[i][2] = dp[i - 2][1] + dp[i - 2][2]return dp[n][1] + dp[n][2]

// c++ 代码示例
int climbingStairsConstraintDP(int n)
{if (n == 1 || n == 2){return 1 ;}vector<vector<int>> dp(n + 1, vector<int>(3, 0)) ;dp[1][1] = 1 ;dp[1][2] = 0 ;dp[2][1] = 0 ;dp[2][2] = 1 ;for (int i = 3 ; i <= n ; i++){dp[i][1] = dp[i - 1][2] ;dp[i][2] = dp[i - 2][1] + dp[i - 2][2] ;}return dp[n][1] + dp[n][2] ;
}