【0321_Week 08】学习总结 #1266

递归、分治、动态规划

• 递归

  • 自己调用自己

  • 代码模板

    public void recur(int level, int param) {
    //1、 terminator  终止条件
        if (level > MAX_LEVEL) {
    //2、 process result 处理过程
        return;
        }
    //3、 process current logic  处理当前逻辑
    	process(level, param);
    //4、 drill down     下沉，进入下层
    	recur(level: level + 1, newParam);
    //5、 restore current status  清理值状态
    }

• 分治

  • 分而治之 Divide & Conquer

  • 思路

    • 寻找最近最简方法，拆解为可重复问题
    • 数学归纳法思维

  • 本质 ：寻找重复性

• 动态规划 DP

  • 理解：即动态递推， 寻找递推方程、递推公式

  • 模式：顺推，动态递推，缓存中间值

  • 常见问题及递推公式

    • 不同路径

      f(x, y) = f(x-1, y) + f(x, y-1)

    • 爬楼梯

      f(n) = f(n - 1) + f(n - 2) , f(1) = 1, f(0) = 0

    • 打家劫舍

      dp[i]状态的定义： max $ of robbing A[0 - > i]
      dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
      
      dp[i][0]状态定义：max  $  of robbing A[0 - > i] 且没偷 nums[i]
      dp[i][1]状态定义：max  $  of robbing A[0 - > i] 且偷了 nums[i]
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
      dp[i][1] = dp[i - 1][0] + nums[i];

    ​

    • 最小路径和

      dp[i][j]状态的定义： minPath(A[1 - > i][1 -> j])
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + A[i][j]

    • 最小路径和

    • 股票买卖

高级动态规划

即高级DP，复杂DP

• 复杂来源：

  1. 状态拥有更多维度（二维、三维、或者更多、甚至需要压缩）

  2. 状态方程更加复杂

• 本质：考察 内功、逻辑思维、数学

• 题型列举

  • 爬楼梯问题改进

    https://leetcode-cn.com/problems/min-cost-climbing-stairs/

  • 编辑距离

字符串

• 基础知识

  • 定义
  • 遍历
  • 比较

• 基础问题

  • 字符串操作问题

  • Anagram异位词问题

  • 回文串问题

• 高级问题及算法

  • 最长子串、子序列
  • 字符串 + 递归 or DP

• 字符串匹配算法

  • 暴力法

  • Rabin-Karp 算法

  • KMP 算法