算法（二）：动态规划

1.抢金币

dp[n]=\begin{cases} w[1] & n=1 \\ max(dp[1],dp[2]) & n=2 \\ max(dp[n-1],dp[n-2]+w[n]) & n\geq3 \end{cases}

第二问随机选一个标号为1

选1就不能选2和n，剩余n-3个房子用第一问求

不选1就等于求等于剩余n-1个房子用第一问求

$max(w[1]+dp[n-3],dp[n-1])$

2.节点选择

如果选择root，最大值=四个孙子树的最大值之和

如果不选择root，最大值=两个子树的最大值之和

dp[n]=\begin{cases} node_n.v & if \ node \ is \ leaf\\ max(node_n.v+\sum dp[n_{grandson}],\sum dp[n_{son}]) & if \ node \ is \ not \ leaf \end{cases}

*3.解码

dp[i]=\begin{cases} 1 & if \ i = 1,0 \\ 0 &if \ S_i=0\ and \ S_{i-1} \ne 1 \ or \ 2\\ dp[i-1]+dp[i-2] & if \ 10<(S_{i-1}*10+S_i)\leq26 \ and \ (S_{i-1}*10+S_i)\neq20\\ dp[i-2] &if \ (S_{i-1}*10+S_i)=10\ or \ 20 \\ dp[i-1] & others \end{cases}

这道题最终可以转化成斐波那契数列进行计算。

首先要确定的是，只有在数值小于26的时候，才可能出现多种解码。

例如，当数字是12，可以解码成AB或者L，当数值大于26则只有唯一解码
例如，当数字是34，解码只有CD

因此可从这个角度出发来解决这个问题，即先对数字进行判断

如果大于2，则进行切分
如果等于二，考虑后面一个数是否大于6
- 如果大于6，则切分
- 不大于6则不变
- 例如：
  - 12213411可以切分成12213、4、11三部分
  - 1227126可以切分为122、7、126三部分
之后对拆分之后的每个子集进行分析，分析的主要依据和之前类似，由于无论如何组合，能够进行解码的数字一定不能是三位数，所以对每一个子集再进行组合，这时候你会发现，在上面讨论的前提下，会形成一个解码个数随子集中元素个数变化的斐波那契数列(这个斐波那契数列没有第一项的1)，求得每个子集解码个数之后，将这些数字相乘就得到了最终结果。

a = input()
b = []
id_head = 0
for i in range(len(a)):
    if int(a[i])>2:
        b.append(a[id_head:i+1])
        id_head = i+1
    elif i == len(a)-1:
            b.append(a[id_head:i + 1])

num = 1
fib = lambda n:1 if n<=2 else fib(n-1)+fib(n-2)

for i in range(len(b)):
    num = num * fib(len(b[i])+1)
print(num)

4.最长连续数列

OPT[i]=max\begin{cases} opt[i-1] & if \ L[i] \ not \ in \ longest \\ i-first[r],r = \sum_{w=0}^{i}L[w] \mod k & if \ L[i] \ in \ longest \end{cases}

j=first[r]是指第一次,即 $arg \min\sum_{w=0}^{j}L[w]=r$

5.最大交易利润

6.最长增序列

opt[i]表示如果找长度为i的单增数列，最小的结尾是opt[i]

nums表示输入的数组

如果nums[j]>opt[i]那么就让opt[i+1]=nums[j]

如果nums[j]<opt[i-1],就去比opt[j-1]、opt[i-2]，

如果opt[1~i-1]都大于nums[j]，更新opt[1]=nums[j]

如果存在opt[m]<nums[j]<opt[n],利用二分法去找n，更新opt[n]=nums[j]

最终len(opt)就是最大长度

opt[i] = \begin{cases} nums[1] &if \ i=1\\ nums[i] &if \ opt[i-1]<nums[i]\\ nums[j] &if \ opt[i-1]<nums[j]<opt[i] \end{cases}

7.机器人移动

令opt[i,j]表示在（i，j）的所有解

opt[i,j]=\begin{cases} top_k[s[1,1]] & if \ i,j=1,1\\ top_k[opt[1,1].join(s[1,2])] & if \ i,j=1,2\\ top_k[opt[1,1].join( s[2,1])]& if \ i,j=2,1\\ top_k[opt[i-1,j].join( s[i,j]) \cup opt[i,j-1].join(s[i,j])] & other \end{cases}

2017年习题

8.最大整除集

将数组从小到大排列，记opt[i]为输入数列遍历到i时最大的整除集长度

opt[i] = \begin{cases} max(opt[j]+1) & if \ s[i]\% s[j]=0\\ 1 & other \end{cases}

9.字符串分割

dp[i]=\begin{cases} 0 & if \ s[i:] is \ palindrome \\ min(dp[j])+1 & for \ j=i+1 \to n \ and \ s[i:j] is\ palindrome \end{cases}

定义状态数组：cut[s.length()+1]，其中：cut[i]代表：string[i…n]字符串从i开始到末尾的最小划分数。
状态转移方程： cut[i] = min(cut[i], cut[j+1]+1); i+1<=j<=n-1
状态转移方程的意思是，string[i…j]是一个回文字符串，所以不用再划分。所以从i开始到末尾以j为划分点的最小划分数为： cut_num_array[j+1]+1 和 cut_num_array[i]中的最小值。
cut_num_array[i]的初值设为：s.length() - i; 也就是按照字符串中的每个字母都单独被划分来计算。

2016年习题

10.蛙跳

青蛙过河，上一次跳k长度，下一次只能跳k-1,k或者k+1。因此对于到达了某一个点，我们可以查看其上一次是从哪个点跳过来的。

设dp[ j ][ i ] 为从i到达j 的步数，初始时把所有的石头存放进hash表。然后设置dp[0][0] = 0. 接着对于每个石头，从可以到达该石头的所有石头中取出步数k(k > 0)，然后当前的stone + k看其是否是合法的石头，是的话就有 d[stone + k ][stone] = k

def can_cross(stones):
    dp = {stone: {} for stone in stones}
    dp[0][0] = 0
    for stone in stones:
        for step in dp[stone].values():
            for k in [step + 1, step, step ‐ 1]:
                if k > 0 and stone + k in dp:
                    dp[stone + k][stone] = k
     return len(dp[stones[‐1]].keys()) > 0

优化

def canCross(self, stones):
    """
        :type stones: List[int]
        :rtype: bool
        """
    stone_set, fail = set(stones), set()
    stack = [(0, 0)]
    while stack:
        stone, jump = stack.pop()
        for j in (jump-1, jump, jump+1):
            s = stone + j
            if j > 0 and s in stone_set and (s, j) not in fail:
                if s == stones[-1]:
                    return True
                stack.append((s, j))
        fail.add((stone, jump))
    return False