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

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

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

因为最近正在复习这方面的算法，下面的笔记是以 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))

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