写点什么

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

用户头像
心在飞
关注
发布于: 2021 年 05 月 05 日

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 动态规划

发布于: 2021 年 05 月 05 日阅读数: 17
用户头像

心在飞

关注

还未添加个人签名 2017.10.15 加入

2个女儿的爸爸 | 程序员 | CS 反恐精英

评论

发布
暂无评论
算法训练营 - 学习笔记 - 第五周