Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

建立动态规划状态转移方程的练习

Posted on 06/01/201506/23/2019 by 四火

algorithm

大学里面算法课老师教导过动态规划,但是就像看书要把书看厚再看薄一样,要把动态规划彻底理解,还是需要一些时间的锻炼。解动态规划问题,每个人都有自己的习惯的套路,我的理解是最核心的过程有两部,一个是找出问题的一个一个子“ 状态”,再一个就是建立“ 状态转移方程”(就是所谓的“ 递推关系式”)。把这个过程搞定,基本上动态规划的题目就解了一半了,剩下那些代码层面的事情,是把思路和数学方程实现而已了。

在实现的过程中,可能会用到一些技巧,比如“ 循环还是递归”,这只是实现的办法而已,不是动态规划的本质;再比如空间换时间,把子问题的解答结果(就是上面说的子“ 状态”)存放起来,减少重复计算,这也是优化的办法,也并非动态规划本质。

因为最近正在复习这方面的算法,下面的笔记是以 LeetCode 上面打着动态规划标签的题目中的一些典型问题为例(我以前做过这些题目的解答汇总),来说明“ 状态识别” 和“ 状态转移方程建立” 这两个步骤的思考过程。这类问题遇到得多了以后,思考就会快一点:

Word Break

【题目】Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

【解答】假设目标字符串 s,长度 i,词典为 dict,f(i) 表示子串 [0,i) 是否可以被“break”,那么,对于所有的以 dict 中的词语 s[k,i) 结尾的 s,只要其中一条的 f(k) 为 true,f(i) 就为 true:

f(i) = (s[k,i) ∈ dict) && f(k)

Word Break II

【题目】Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = "catsanddog",

dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

【解答】还是从后往前考虑,目标字符串 s,长度 i,break 的结果集为 f(i),考虑所有以词典 dict 中词语 s[k, i) 结尾的情况,在相应的 f(k) 的结果集中加上 s[k, i) 即可。

f(i) = f(k) + s[k, i), s[k,i) ∈ dict

Unique Paths

【题目】A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

【解答】假设当格子 [i, j] 处为终点时,unique path 的数量为 f(i, j),那么存在如下递推关系,其中考虑取值情况时,i-1 和 j-1 都必须不小于 0:

f(i) = f(i-1, j) + f(i, j-1)

Unique Binary Search Trees

【题目】Given n, how many structurally unique BST's (binary search trees) that store values 1…n?

For example,

Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

【解答】BST 有个要求,就是左子树的所有数都小于根,右子树的所有数都大于根。假设 f(i, j) 表示已升序排序的数组 [i,j] 所存在的不同 BST 的集合,那么从 i 到 j,每个元素都可以成为根,每确定一次根,就确定了一次左右子树的划分:

f(i, j) = f(i, k-1) * f(k+1, j), k>=i && k<=j

Triangled

【题目】Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

【解答】假设从上至下的第 i 层,第 k 个元素值为 v[i][k],从下往上积累得到的最短路径值为 f(i, k),那么:

f(i, k) = min( f(i+1, k), f(i+1, k+1) ) + v[i][k]

Palindrome Partitioning II

【题目】Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

【解答】假设目标字符串 s,长度为 len,f(i) 表示子串 s[i, len) 的最小 cut 数目,现在这个数目绝对不会大于 len-i,那么在 i 的右边切一刀,保证这一刀的右边是回文,满足这个条件的情况下,考虑这一刀可以切的所有位置,找最小值。

f(i) = min(len-i, f(k+1)+1), k>0 && k<len && s[k+1, len) 是回文

Maximum Subarray

【题目】Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

【解答】假设以 i 结尾的数组 nums[0 ,i] 的最大子数组为 f(i),那么:

f(i) = max(f(i-1)+nums[i], nums[i])

Interleaving String

【题目】Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:

s1 = "aabcc",

s2 = "dbbca",

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

【解答】假设 f(i, j) 表示 s1 的前 i 个字符 s1[0, i) 和 s2 的前 j 个字符 s2[0, j) 能否形成 s3 的前 i+j 个字符,于是:

f(i, j) = (f(i, j-1) && s2[j-1]==s3[i+j-1]) || (f(i-1, j) && s1[i-1]==s3[i+j-1])

Edit Distance

【题目】Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

【解答】f(i, j) 表示 word1 的子串 word1[0, i) 到 word2 的子串 word[0, j) 的编辑距离,那么,考虑 insert、replace 和 delete 三种情况:

insert: f1(i, j) = f(i-1, j) + 1

replace: f2(i, j) = f(i-1, j-1) + 1

delete: f3(i, j) = f(i, j-1) + 1

因此:

f(i, j) = min(f1(i, j), f2(i, j), f3(i, j))

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. 再谈大楼扔鸡蛋的问题
  2. 排序算法一览(上):交换类、选择类和插入类排序
  3. LeetCode 题目解答——Medium 部分(上)
  4. LeetCode 付费题目(一)
  5. LeetCode 题目解答—— 第 372 到 415 题

1 thought on “建立动态规划状态转移方程的练习”

  1. CRIMX says:
    06/28/2018 at 12:58 PM

    感谢分享!这几天照着来练习受益匪浅。

    Unique Binary Search Trees 方程那里写漏了求和。另外还可以优化为一维,因为 2-3-4 等价为 1-2-3 。
    所以
    f(i) = Σ f(k-1) * f(i-k), 1 <= k <= i
    f(i) = 1, i <= 1

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme