综合练习与复习

Array Hopper I

Dictionary Word I

Longest increasing subsequence(LIS) series

区间DP

股票系列及多状态DP问题

DP IV

Date: April 23, 2023

Topic: Dynamic Programming I

Recall

Introduction

Fibonacci

Longest Ascending subarray

Maximal product when cutting rope

Dictionary Problem

Jump Game

Notes

• DP本质：induction是从个例到个性（规律）的推演过程

• 解题过程

  • 读题，抽取核心信息
  • 枚举case1，case2， case3
  • 枚举的过程，不断思考：有什么规律可循，如何查表
  • 找到规律后，用英文描述induction rule，再描述成数学表达式，并继续推演以验证正确性

• Recursion + Memoization

  • Memo：见过就读，没见过就存
  • Use an Integer[]
  • Use a HashMap
  • TC: O(n)
  • Space: O(n) on heap + O(n) on call stack

• Dynamic Programming

  • DP解题的方式就是如何定义表格里每个element的意义，以及把表格里的value填满
  • base case：F(0) = 0, F(1) = 1
  • induction rule: F(i) represents i-th fibonacci number which is the sum of F(i - 1) and F(i - 2)
  • Return F(n)
  • TC: O(n)
  • SC: O(n) on heap rather than the recursion way O(n) on call stack
  • Optimize to O(1) as we only care about the 2 previous values

• 核心思想类似于数学归纳法

• 把一个大问题的解决方案用比他小的问题

• Subarray: 连续contiguous elements in an array

• Subsequence:不一定连续 not necessarily contiguous（can jump）

• base case: only one element M[0] = 1

• induction rule: M[i] represents the max length of the ascending subarray with the range of [0, i](including the i-th element)

• return: global max

• TC: O(n)

• SC: O(n) → Optimize to O(1)

• Solution 1: DFS (recursion)

  • TC: O(n!)
  • SC:O(n) on call stack

• solution 2: DP(左大段 + 右小段思想）

• Base case：M[0] = invalid, M[1] = invalid

• induction rule: M[i] represents the maximal product of

• M[i] = max(max(j, M[j]) * (i -j) where 1 < = j < i

• TC: O(n^2)

• SC: O(n)

• TC: O(n^3)

• SC: O(n)

<aside> 📌 SUMMARY:Linear scan and look back

</aside>

Date: April 26, 2023

Topic: DP II

Recall

小青蛙问题

Minimum number of Jumps

Longest Sum of a Subarray

<aside> 📌 SUMMARY:

</aside>