算法训练营 - 学习笔记 - 第五周

5.1 五天小长假补补课，把之前落下的课程补回来。

划重点

失败只有一种，那就是半途而废！

比别人多一点执着，你就会创造奇迹！

坚持

1. 五毒神掌

2. 脑图 + 笔记总结

3. 微信群里多交流

感触

• 人肉递归低效、很累

• 找到最近最简方法，将其拆解成可重复解决的问题

• 数学归纳法思维（抵制人肉递归的诱惑）

• 本质：寻找重复性 -> 计算机指令集

已学数据结构与算法

Array 数组 Search 查询

Linked List 链表 Recursion 递归

Stack 栈 DFS 深度优先搜索

Queue 队列 BFS 广度优先搜索

HashTable 哈希表 Divide & Conquer 分治

Set, Map Backtracking 回溯

Tree 二叉树 Greedy 贪心

BST 二叉搜索树 Binary Search 二叉查找

推荐网站： Visual Go .net

动态规划（一）

递归

public void recur(int level, int param) {  // terminator  if (level > MAX_LEVEL) {    // process result    return;  }    // process current logic  process(level, param);    // drill down    recur(level: level + 1, param);    // restore current status}  

分治

把大问题分解成若干个子问题

动态规划 Dynamic Programming

1. "Simplifying a complicated problem by breaking it down into simpler sub-problems"(in a recursive manner)

2. Divide & Conquer + Optimal substructure

3. 不需要保存中间结果

关键点

动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）

共性：找到重复子问题

差异性：最优子结构、中途可以淘汰次优解（复杂度更低）

DP 例题解析：Fibonacci 数列、路径计数

Fibonacci： 使用缓存存储中间结果，傻递归：指数级

int fib(int n, int[] memo) {  if ( n <= 1) {    return n;  }    if (memo[n] == 0) {    memo[n] = fib(n - 1) + fib(n - 2);  }  return memo[n];}

递推

a[0] = 0, a[1] = 1;

for (int i = 2; i <=n; i++) {

a[i] = a[i-1] + a[i-2];

}

Count the paths(二维)

opt[i, j] = opt[i+1, j] + opt[i, j+1]

完整逻辑：

if a[i, j] = '空地':

opt[i, j] = opt[i+1, j] + opt[i, j+1]

else:

opt[i, j] = 0

动态规划关键点

1. 最优子结构

2. opt[n] = best_if(opt[n-1], opt[n-2])

3. 存储中间状态

4. opt[i]

5. 递推公式

6. Fib: opt[n-1] + opt[n-2]

DP 例题解析：最长公共子序列

不同路径：递推

1. 从（i, j）走到 <end> 的不同路径数

2. 从 <start> 走到 （i, j）的不同路径数

public int uniquePaths(int m, int n) {  int[][] dp = new int[m][n];  for (int i = m - 1; i >= 0; i--) {    for (int j = n - 1; j >= 0; j--) {      if (i == m - 1 || j == n - 1) {        dp[i][j] = 1;      } else {        dp[i][j] = dp[i+1][j] + dp[i][j+1];      }     }  }  return dp[0][0];}  

最长公共子序列

1. 暴力求解：取或不取

2. 找重复 -> 二维数组递推，定义状态方程，空间

3. DP 方程

4. if S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1])

5. if S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1-1, s2-1] + 1

动态规划小结

1. 打破自己的思维惯性，形成机器思维

2. 理解复杂逻辑的关键

3. 也是职业进阶的要点要领，不要人肉递归

MIT 动态规划