大学里面算法课老师教导过动态规划,但是就像看书要把书看厚再看薄一样,要把动态规划彻底理解,还是需要一些时间的锻炼。解动态规划问题,每个人都有自己的习惯的套路,我的理解是最核心的过程有两部,一个是找出问题的一个一个子“状态”,再一个就是建立“状态转移方程”(就是所谓的“递推关系式”)。把这个过程搞定,基本上动态规划的题目就解了一半了,剩下那些代码层面的事情,是把思路和数学方程实现而已了。
在实现的过程中,可能会用到一些技巧,比如“循环还是递归”,这只是实现的办法而已,不是动态规划的本质;再比如空间换时间,把子问题的解答结果(就是上面说的子“状态”)存放起来,减少重复计算,这也是优化的办法,也并非动态规划本质。
因为最近正在复习这方面的算法,下面的笔记是以LeetCode上面 打着动态规划标签的题目 中的一些典型问题为例(我以前做过这些题目的解答汇总),来说明“状态识别”和“状态转移方程建立”这两个步骤的思考过程。这类问题遇到得多了以后,思考就会快一点:
【题目】 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)
【题目】 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
【题目】 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)
【题目】 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
【题目】 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]
【题目】 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)是回文
【题目】 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])
【题目】 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])
【题目】 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))