算法学习笔记（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) - 1
if 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) - 1
if 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 1
dp = [ [0] * 3 for _ in range(n + 1)]
dp[1][1], dp[1][2] = 1, 0
dp[2][1], dp[2][2] = 0, 1
for 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] ;
}解析：
在上面的约束条件中只需要考虑一个约束对象，因此我们可以通过扩展状态定义，使得问题重新满足无后效性，
给定一个共有 i 阶的楼梯，你每步可以上 1 阶或者 2 阶。规定当爬到第 i 阶时，系统自动会在第 2i 阶上放上障碍物，之后所有轮都不允许跳到第 2i 阶上。例如，前两轮分别跳到了第 2、3 阶上，则之后就不能跳到第 4、6 阶上。请问有多少种方案可以爬到楼顶？
在这个问题中，下次跳跃依赖过去所有的状态，因为每一次跳跃都会在更高的阶梯上设置障碍，并影响未来的跳跃。对于这类问题，动态规划往往难以解决。
实际上，许多复杂的组合优化问题（例如旅行商问题）不满足无后效性。对于这类问题，我们通常会选择使用其他方法，例如启发式搜索、遗传算法、强化学习等，从而在有限时间内得到可用的局部最优解。
原文地址：https://blog.csdn.net/2301_76874968/article/details/140287377
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！