区块链技术博客
www.b2bchain.cn

算法-动态规划

这篇文章主要介绍了算法-动态规划,通过具体代码讲解6034并且分析了算法-动态规划的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-动态规划。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6034。具体如下:

算法 动态规划

算法

发布日期:   2019-12-02
文章字数:   371
阅读时长:   1 分
阅读次数:  

动态规划:博弈型

博弈型dp一般从第一步分析,而不是最后一步,需要开n+1

1、LintCode 394 Coins in a Line

【问题】有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定 先手玩家必胜还是必败?

【分析】从第一步开始,一开始有n个硬币,A可以拿一个或两个硬币,这样B则对应拿n-1个或n-2个硬币,A肯定会采取策略让自己获胜。然后不断拿。假设一开始有5个硬币,可以画出如果所示的树形结构,必败就是自己无路可逃,必胜就是有赢的可能。

算法-动态规划

【状态】设dp[i]表示面对i个硬币,是否先手必胜则有下面几种情况

  • dp[i] = true,f[i-1]==false || f[i-2]==false(对手拿1个或2个都是必败的情况)
  • dp[i] = false,f[i-1]==true && f[i-2]==true(对手拿1个或2个都是必胜的情况)

【初始情况与边界】

  • dp[0] = 0,面对0个硬币,必败
  • dp[1] = dp[2] = true
public boolean firstWillWin(int n) {         if (n == 0) {             return false;         }         if (n <= 2) {             return true;         }         boolean[] dp = new boolean[n + 1];         dp[0] = false;         dp[1] = true;         for (int i = 2; i <= n; i++) {             // if (dp[i - 1] == true && dp[i - 2] == true) {             //     dp[i] = false;             // } else {             //     dp[i] = true;             // }             dp[i] = !dp[i - 1] || !dp[i - 2];         }         return dp[n];     }


算法 动态规划

动态规划:划分型划分型动态规划就是给定长度为N的字符串,需要划分成若干段,段数不限,每一段满足一定的性质。在学校oj中做过的书本分发、漆狗屋这种就属于划分型。开数组也是开n+1 1、Lintcode 512 解码方法【问题】有一个消息包含A
2019-12-02 算法
动态规划解题模版::坐标型坐标型dp一般都是给定网格、序列,来求满足某种性质的最大值、最小值。开数组时,f[i]代表以ai 结尾的满足条件的子序列,f[i][j]代表以i、j结尾的满足条件的某种情况。 做题思路: 从最后一步出发思考,确定
2019-12-02 算法

本文地址https://www.b2bchain.cn/?p=6034

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-动态规划
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们