动态规划
思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
LIS问题
有一个长为n的数列a0, a1, ......, a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列，该问题被称为最长上升子序列（LIS，Longest Increasing Subsequence）问题。
例子：
LIS问题描述：给出一个数列A，求A的一个长度最大的子数列B，使得B是一个递增数列。
例如：数列A：5，2，8，6，3，6，9，7一个递增的子数列为5，8，9； 一个长度最大的递增子数列为2，3，6，9或者2，3，6，7，则其最大长度为4。
给定一个数组，求其的一个长度最大的子数列的长度。
暴力破解法：
思路：- 在序列[5，2，8，6，3，6，9，7]中我们首先判断以5开头的递增子序列，再继续判断5之后应当接什么数字。
- 使用循环判断，我们可以轻易知道，下一个数字应当有8，6，6，9，7，接下来我们判断以8，6，6，9，7开头最长子序列。即判断[8，6，3，6，9，7]，[6，3，6，9，7]，[6，9，7]，[9，7]，[7]的最长子序列。
- 我们发现我们可以使用分治法解决这个问题。
import time def solution(arr, index): max_len = 1 if index == len(arr) - 1: return 1 for i in range(index + 1, len(arr)): if arr[i] > arr[index]: max_len = max(max_len, solution(arr, i) + 1) return max_len def LTS(arr): result = [] for i in range(len(arr)): result.append(solution(arr, i)) return max(result) t1 = time.time() array = [220, 183, 190, 67, 832, 596, 67, 820, 187, 74, 888, 774, 398, 987, 403, 14, 39, 378, 506, 400, 158, 946, 195, 70, 494, 910, 863, 438, 996, 470, 213, 86, 950, 727, 476, 159, 573, 899, 321, 922, 310, 673, 294, 812, 322, 882, 340, 387, 375, 812, 869, 492, 459, 731, 225, 92, 2, 299, 867, 21, 84, 479, 61, 223, 211, 362, 131, 457, 292, 819, 927, 408, 573, 215, 295, 170, 278, 355, 357, 131, 101, 153, 120, 347, 874, 946, 974, 858, 643, 252, 263, 443, 974, 476, 471, 159, 435, 488, 189, 228] print(LTS(array)) print("time:",time.time() - t1)结果：
15 time: 11.03683352470398动态规划：对暴力破解法的改进
- 我们在对[5，2，8，6，3，6，9，7]序列时一定会求[8，6，3，6，9，7]，[6，3，6，9，7]，[6，9，7]，[9，7]，[7]的最长子序列；
- 而我们在求[8，6，3，6，9，7]的最长子序列时，已经求过了[9，7]的最长子序列，也就是说[9，7]的最长子序列我们不用再求，我们只需要在求[8，6，3，6，9，7]子序列时保存[9，7]的子序列的最长子序列的值。
- 当我们去求[9，7]的最长子序列的值的时候，直接取值就行。
import time def solution(arr, index): if index in memo: return memo[index] max_len = 1 if index == len(arr) - 1: return 1 for i in range(index + 1, len(arr)): if arr[i] > arr[index]: max_len = max(max_len, solution(arr, i) + 1) memo[index] = max_len return max_len def LTS(arr): result = [] for i in range(len(arr)): result.append(solution(arr, i)) return max(result) memo = {} t1 = time.time() # print(t1) array = [220, 183, 190, 67, 832, 596, 67, 820, 187, 74, 888, 774, 398, 987, 403, 14, 39, 378, 506, 400, 158, 946, 195, 70, 494, 910, 863, 438, 996, 470, 213, 86, 950, 727, 476, 159, 573, 899, 321, 922, 310, 673, 294, 812, 322, 882, 340, 387, 375, 812, 869, 492, 459, 731, 225, 92, 2, 299, 867, 21, 84, 479, 61, 223, 211, 362, 131, 457, 292, 819, 927, 408, 573, 215, 295, 170, 278, 355, 357, 131, 101, 153, 120, 347, 874, 946, 974, 858, 643, 252, 263, 443, 974, 476, 471, 159, 435, 488, 189, 228] print(LTS(array)) print("time:",time.time() - t1)15 time: 0.000995635986328125
机器人走路
问题：一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。问总共有多少条不同的路径走到右下角。
def robots(pos_x, pos_y):
global status
if status[pos_x][pos_y] != 0:
return status[pos_x][pos_y]
next_x = pos_x - 1 if pos_x - 1 >= 0 else 0
next_y = pos_y - 1 if pos_y - 1 >= 0 else 0
count1 = 0
count2 = 0
if next_x != pos_x:
count1 = robots(next_x, pos_y)
if next_y != pos_y:
count2 = robots(pos_x, pos_y - 1 if pos_y - 1 >= 0 else 0)
status[pos_x][pos_y] = count1 + count2
return count1 + count2
if __name__ == '__main__':
m = 7
n = 4
status = [[0 for i in range(n)] for j in range(m)]
status[0][1] = 1
status[1][0] = 1
print(robots(m - 1, n - 1))
for item in status:
print(item)青蛙跳台阶
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个7级的台阶总共有多少种跳法。
memo = {}
def jump(step):
if step in memo:
return memo[step]
if step == 1:
return 1
if step == 2:
return 2
step_count1 = jump(step - 1)
step_count2 = jump(step - 2)
memo[step] = step_count2 + step_count1
print("跳到第{}级台阶时，有{}种跳法".format(step, step_count1 + step_count2))
return step_count2 + step_count1
if __name__ == '__main__':
jump(7)
Comments | NOTHING