自学内容网 自学内容网

算法学习笔记(8.1)-动态规划入门

目录

问题特性:

最优子结构:

代码示例:(动态规划最优子结构)

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

代码示例:

无后效性:

解析:

具体过程图示如下:

具体的代码示例:

解析:

问题特性:

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

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

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

最优子结构:

给定一个楼梯,你每步可以上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. 当上一轮跳了1阶时,上上一轮只能选择跳2阶,即dp[i,1]只能从dp[i-1,2]转移过来
  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)!