Data Structure and Algorithms
  • Introduction
  • 面经
    • 亚马逊面经
  • Sorting
    • Quick Sort
    • Merge Sort
    • Heap Sort
  • Palindrome
    • Check String Palindrom
    • Palindrome Partitioning
    • Palindrome Partitioning II
    • Longest Palindromic Substring
    • Valid Palindrome
  • Linked List
    • Remove Duplicates from Sorted List
    • Remove Duplicates from Sorted List II
    • Remove Nth Node From End of List
    • Remove Linked List Elements
    • Remove Duplicates from Unsorted List
    • Remove duplicate Circular Linked list
    • Reverse Linked List
    • Reverse Linked List II
    • Reverse Nodes in k-Group
    • Partition List
    • Insertion Sort List
    • Reorder List
    • Linked List Cycle
    • Rotate List
    • Merge k Sorted Lists
    • Copy List with Random Pointer
    • Nth to Last Node in List
    • Add Two Numbers
    • Add Two Numbers II
    • Palindrome Linked List
  • Binary Search
    • Sqrt(x)
    • Search a 2D Matrix
    • Search a 2D Matrix II
    • Search Insert Position
    • First Position of Target
    • Last Position of Target
    • Count of Smaller Number
    • Search for a Range
    • Search in a Big Sorted Array
    • First Bad Version
    • Find Minimum in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array II
    • Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Find Peak Element*
    • Recover Rotated Sorted Array
    • Rotate String
    • Wood Cut
    • Total Occurrence of Target
    • Closest Number in Sorted Array
    • K Closest Number in Sorted Array
    • Maximum Number in Mountain Sequence
    • Search Insert Position *
    • Pow(x, n)
    • Divide Two Integers
  • Graph
    • Clone Graph
    • Topological Sorting
    • Permutations
    • Permutations II
    • Subsets
    • Subsets II
    • Word Ladder
    • Word Ladder II
    • N-Queens
    • N-Queens II
    • Connected Component in Undirected Graph
    • Six Degrees
    • String Permutation II
    • Letter Case Permutation
  • Data Structure
    • Min Stack
    • Implement a Queue by Two Stacks
    • Largest Rectangle in Histogram
    • Max Tree
    • Rehashing
    • LRU Cache
    • Subarray Sum
    • Anagrams
    • Longest Consecutive Sequence
    • Data Stream Median
    • Heapify
    • Ugly Number
    • Ugly Number II
  • Misc
    • PlaceHolder
    • Fibonacci
  • Array and Numbers
    • Merge Sorted Array
    • Merge Two Sorted Arrays
    • Median of two Sorted Arrays
    • Best Time to Buy and Sell Stock
    • Best Time to Buy and Sell Stock II
    • Best Time to Buy and Sell Stock III
    • Maximum Subarray
    • Maximum Subarray II
    • Maximum Subarray III
    • Minimum Subarray
    • Maximum Subarray Difference
    • Subarray Sum
    • Subarray Sum Closest
    • Two Sum
    • 3Sum
    • 3Sum Closest
    • 4Sum
    • k Sum
    • k Sum II
    • Partition Array
    • Sort Letters by Case
    • Sort Colors
    • Sort Colors II
    • Interleaving Positive and Negative Numbers
    • Spiral Matrix
    • Spiral Matrix II
    • Rotate Image
  • Dynamic Programming I
    • Triangle
    • Minimum Path Sum
    • Unique Paths
    • Unique Paths II
    • Climbing Stairs
    • Jump Game
    • Jump Game II
    • 01 Matrix
    • Longest Line of Consecutive One in Matrix
    • Shortest Path in Binary Matrix
  • Dynamic Programming II
    • Word Break
    • Longest Common Subsequence
    • Longest Common Substring
    • Edit Distance
    • Distinct Subsequences
    • Interleaving String
    • k Sum
  • Binary Tree And Divide Conquer
    • Binary Tree Preorder Traversal*
    • Binary Tree Inorder Traversal*
    • Binary Tree Postorder Traversal*
    • Maximum Depth of Binary Tree
    • Minimum Depth of Binary Tree
    • Balanced Binary Tree
    • Lowest Common Ancestor
    • Binary Tree Maximum Path Sum
    • Binary Tree Maximum Path Sum II
    • Binary Tree Level Order Traversal*
    • Binary Tree Level Order Traversal II
    • Binary Tree Zigzag Level Order Traversal
    • Validate Binary Search Tree
    • Inorder Successor in Binary Search Tree
    • Binary Search Tree Iterator
    • Search Range in Binary Search Tree
    • Insert Node in a Binary Search Tree
    • Remove Node in Binary Search Tree
    • Find the kth largest element in the BST
    • Kth Smallest Element in a BST
    • Serialize and Deserialize Binary Tree*
    • Construct Binary Tree from Preorder and Inorder Traversal
    • Convert Sorted Array to Binary Search Tree
    • Unique Binary Search Trees *
    • Unique Binary Search Trees II *
    • Recover Binary Search Tree
    • Same Tree
    • Symmetric Tree
    • Path Sum*
    • Path Sum II*
    • Flatten Binary Tree to Linked List
    • Populating Next Right Pointers in Each Node
    • Sum Root to Leaf Numbers
    • Binary Tree Right Side View
    • Count Complete Tree Nodes
    • Invert Binary Tree
    • Binary Tree Paths*
    • Subtree of Another Tree
  • A家面试总结
  • Expedia面经收集
  • Python 常用语句
  • lotusflare
  • Microsoft
  • 模板
  • Bing 组面试总结
  • 面试笔记
  • Sliding window
Powered by GitBook
On this page
  • 动态规划的四点要素
  • 状态State
  • 方程Function
  • 初始化Initialization
  • 答案Answer
  • 面试中常见的动态规划类型

Was this helpful?

Dynamic Programming I

解决方法:

  • DFS: Traverse

  • DFS: Divide Conquer

  • Divide Conquer + Memorization

  • Traditional Dynamic Programming

多重循环vs记忆化搜索

动态规划可以使用多重循环与递归的方式实现，但是多重循环比较容易理解。

自底向上vs自顶向下

两种方法没有太大优劣区别思维模式一个正向，一个逆向

什么情况下
使用
动态规划?

满足下面三个条件之一:

  • ● 求最大值最小值

  • ● 判断是否可行

  • ● 统计方案个数

动态规划的四点要素

状态State

灵感，创造力，存储小规模问题的结果

方程Function

状态之间的联系，怎么通过小的状态，来算大的状态

初始化Initialization

最极限的小状态是什么,起点

答案Answer

最大的那个状态是什么，终点

面试中常见的动态规划类型

坐标型动态规划15%

序列型动态规划30%

双序列动态规划30%

划分型动态规划10%

背包型动态规划10%

区间型动态规划5%

PreviousRotate ImageNextTriangle

Last updated 4 years ago

Was this helpful?