动态规划算法练习 (1)

动态规划(英语:Dynamic programming,简称DP)是一种在数学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。在生物信息领域,比如在序列比对的时候,就用到了动态规划的思想。在隐马尔科夫模型中的维特比 (Viterbi) 算法也使用了动态规划算法。

对于一个问题,我们分析出初始状态和递推公式是解出的关键。比如以下几个经典题目:

1. 爬楼梯 (https://leetcode.com/problems/climbing-stairs/)

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

这个问题仔细想想其实与斐波那契数列很像,同样可用递归求解。 假如最后我们已经爬上了10层,那么最后一个步骤走了要么一步, 要么两步。也就是说,我们到10层的走法,其实就是我们走到八层和九层的方法的和。即F(n) = F(n-2) + F(n-1)。

递归求解:

def climb(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climb(n - 1) + climb(n - 2)

climb(10)

递归会很慢,浪费很多没必要的资源。可以考虑以下方法:

def climb(n):
    way = [0] * n
    way[0] = 1
    way[1] = 2
    for i in range(2, n):
        way[i] = way[i - 1] + way[i - 2]
    return way[n - 1]

# 或者 
def climb=(n):
    if n <= 2:
        return n
    else:
        a, b = 1, 2
        for i in range(n - 2):
            a, b = b, a + b
        return b

climb(10)
2. 使用最小花费爬楼梯 (https://leetcode.com/problems/min-cost-climbing-stairs/)

数组的每个索引做为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。(cost 的长度将会在 [2, 1000]。) 比如:

与上一个题有异曲同工之妙,其实其实本质上i位置的值就等于前一个和前两个中的最小值与这个位置的值的和,即f[i] = cost[i] + min(f[i-1], f[i-2])。

 def cal_cost(cost):
        dp = [0] * (len(cost) + 1)
        dp[0] = cost[0]
        dp[1] = cost[1]
        
        cost.append(0)
        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i-2]) + cost[i]
            
        return dp[-1]
3. 打家劫舍 (https://leetcode.com/problems/house-robber/)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

当我们偷窃到第i家的时候,所能偷到的就是一直到第i - 1家所偷到的与第i - 2家和第i家偷到的钱的和的最大值,即dp[i] = max(nums[i] + dp[i -2], dp[i-1])。

def rob(nums):
    size = len(nums)
    
    if size == 1:
        return nums[0]
    elif size == 2:
        return max(nums[0], nums[1])
    elif size == 0:
        return 0     
    else:
        dp = [0] * size
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, size):
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])

        return dp[-1]

其实可以发现我们其实只用到了dp[i-2]与dp[i-1]的值,那么对上边的方法进行优化:

def rob(nums):
    now = last = 0
    for i in range(len(nums)):
        now, last = max(last + nums[i], now), now 
    return now 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划算法练习(5)--medium

    中文链接:https://leetcode-cn.com/problems/predict-the-winner/ 英文链接:https://leetcode...

    生信编程日常
  • R中t()转置后为什么会变成字符型数据

    数值型数据全部变成了字符型,怎么回事?其实是因为cluster那一列数据并不是数值型,而是字符型。因为这一列代表某一群细胞,如cluster0.所以才会出现这个...

    生信编程日常
  • 动态规划算法练习 (2)

    爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。 最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作: 选出任一 x,满足 0 < ...

    生信编程日常
  • 小姐姐提灯给你讲讲动态规划(万字长文)

    我们把要解决的一个大问题转换成若干个规模较小的同类型问题,当我们求解出这些小问题的答案,大问题便不攻自破。这就是动态规划。

    程序员小浩
  • 动态规划入门看这篇就够了,万字长文!

    今天是小浩算法 “365刷题计划” 动态规划 - 整合篇。大家应该期待已久了吧!奥利给!

    程序员小浩
  • 干货:图解算法——动态规划系列

    讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。概念中的各阶段之间的关系,其实指的就是状态转移方程。很...

    宜信技术学院
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地
  • 陕西师范大学第七届程序设计竞赛网络同步赛 iko和她的糖

    dp[i][j]=max(dp[i][j],dp[i-1][j]-b[i-1]);

    用户2965768
  • 一天一大 leet(戳气球)难度:困难-Day20200719

    有 n 个气球,编号为 0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

    用户6549452
  • dp经典问题

    输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    用户7625070

扫码关注云+社区

领取腾讯云代金券