CS
Algorithm
Algorithmmaster
Algorithm
Algorithmmaster
  • lintcode
  • EPI
    • String
      • Base Convert
  • Graph
    • Inorder Successor in BST
    • Balanced Binary Tree
    • All Paths From Source to Target
  • LinkedIn
    • House robber II
    • Single Number
    • Flatten Binary Tree to Linked List
    • Smallest Difference pair of values between two unsorted Arrays
    • Word Search II
    • Implement Trie (Prefix Tree)
    • K Closest Points
    • implement BST
    • HashMap
    • Implement strStr()
    • Min Stack
    • Meeting Rooms
    • Shortest Completing Word
    • Longest Palindromic Substring
    • Longest Palindromic Subsequence
    • Count Different Palindromic Subsequences
    • Palindromic Substrings
    • Sparse Matrix Multiplication
    • Insert Delete GetRandom O(1) - Duplicates allowed
    • Bulb Switcher
    • Verify Preorder Sequence in Binary Search Tree
    • Untitled
    • Find the Celebrity
    • Coin Change
    • Partition Equal Subset Sum
    • Permutation Sequence
    • Next Permutation
    • Kth Smallest Element in a BST
    • Word Search
    • Word Break
    • Shuffle an Array
    • Add Two Numbers
    • Longest Substring Without Repeating Characters
    • Longest Increasing Subsequence
    • 3Sum Smaller
    • LFU Cache
    • Copy List with Random Pointer
    • Linked List Cycle
    • Merge Sorted Array
    • Two Sum II - Input array is sorted
    • Search Insert Position
    • Find First and Last Position of Element in Sorted Array
    • Combination Sum
    • Path Sum
    • Roman to Integer
    • Valid Parentheses
    • Product of Array Except Self
    • Permutations
    • 3Sum
    • Reverse Integer
    • Longest Common Subsequence and substring
    • Implement Stack using Queues
    • Sort Characters By Frequency
    • Delete Node in a BST
    • Invert Binary Tree
    • Serialize and Deserialize BST
    • Reverse String
    • Binary Tree Zigzag Level Order Traversal
    • Friend Circles
    • Letter Combinations of a Phone Number
    • Fizz Buzz
    • Encode and Decode TinyURL
    • Binary Tree Right Side View
    • Shortest Word Distance III
    • Binary Search Tree Iterator
    • Kth Largest Element in an Array
    • Clone Graph
    • Lowest Common Ancestor III
    • Lowest Common Ancestor II
    • Reverse Words in a String
    • Path Sum
    • Find K Pairs with Smallest Sums
    • Validate Binary Search Tree
    • All O`one Data Structure
    • Top K Frequent Elements
    • Integer to Roman
    • Shortest Word Distance III
    • Edit Distance
    • Profitable Schemes
    • Minimum Window Substring
    • LRU Cache
    • Text Justification
    • Integer to English Words
    • Partition to K Equal Sum Subsets
    • Graph Valid Tree
    • Exclusive Time of Functions
    • Repeated DNA Sequences
    • Valid Number
    • Insert Delete GetRandom O(1)
    • Same Tree
    • Friends Within Three Jumps
    • Isomorphic Strings
    • Sum of Square Numbers
    • Valid Perfect Square
    • Evaluate Reverse Polish Notation
    • House Robber
    • Palindromic Substrings
    • Find Largest Value in Each Tree Row
    • Can Place Flowers
    • Insert Interval
    • Maximum Depth of Binary Tree
    • Two Sum
    • Paint House II
    • Max Points on a Line
    • Word Ladder II
    • Word Ladder
    • Validate IP Address
    • Maximum Product Subarray
    • Factor Combinations
    • Flatten Nested List Iterator
    • Max Stack
    • Number of Connected Components in an Undirected Graph
    • Combination Sum II
    • Permutations II
    • Permutations
    • Climbing Stairs
    • Paint House
    • Closest Binary Search Tree Value
    • Closest Binary Search Tree Value II
    • Rotate String
    • Max Area of Island
    • Maximum Subarray
    • Serialize and Deserialize Binary Tree
    • Second Minimum Node In a Binary Tree
    • Lowest Common Ancestor of a Binary Tree
    • Lowest Common Ancestor of a Binary Search Tree
    • Symmetric Tree
    • Binary Tree Upside Down
    • Maximum Depth of Binary Tree
    • Find Leaves of Binary Tree
    • Number of Islands
    • Nested List Weight Sum II
    • Nested List Weight Sum
    • Merge Intervals
    • Valid Triangle Number
    • Find K Closest Elements
    • Find Smallest Letter Greater Than Target
    • Pow(x,n)
    • Search in Rotated Sorted Array II
    • Search in Rotated Sorted Array
    • Sqrt(x)
    • Intersection of Two Linked Lists
    • Binary Tree Level Order Traversal
    • Shortest Word Distance
    • Two Sum III - Data structure design
    • Shortest Word Distance II
  • Binary Search
    • Find K Closest Elements
    • Find Min In Rotated Sorted Array
    • Find Peak Element
    • First Bad Version
    • First Position Of Target
    • Guess Num Higer Or Lower
    • Last Position Of Target
    • Longest Increasing Subsequence
    • Russian Doll Envelopes
    • Search In Big Sorted Array
    • Search Insert Position
    • Single Number IV
    • pow(x,n)
    • sqrt
    • Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Find Minimum in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array II
    • Search for a Range
    • Intersection of Two Arrays
    • Count of Smaller Numbers After Self
  • Binary Tree
    • 107. Binary Tree Level Order Traversal II
    • Lowest Common Ancestor of a Binary Tree
    • Lowest Common Ancestor of a Binary Tree II
    • Lowest Common Ancestor III
    • preorder Traversal
    • Inorder traversal
    • Binary Tree Path
    • post Order traversal
    • Level Traversal
    • Serialize and Deserialize Binary Tree 07/25
    • Find Leaves of Binary Tree 07/25
    • Sum of Left Leaves 07/25
    • Recover Binary Search Tree 07/26
    • Check Full Binary Tree 07/26
    • Binary Tree Longest Consecutive Sequence07/26
    • Equal Tree Partition 07/27
    • Same Tree 07/27
    • Sum Root to Leaf Numbers 07/26
    • Binary Search Tree Iterator 07/28
    • Preorder morris traversal 07/29
    • inorder traversal morris 07/29
  • BFS
    • Search Graph Nodes 07/30
    • Is Graph Bipartite? 07/30
    • Walls and Gates 07/30
    • Clone Graph 07/30
    • Word Ladder 07/30
    • Topological Sorting 08/01
    • Course Schedule 08/03
    • Course Schedule II 08/04
  • DFS
    • Target Sum 08/06
    • Minimum Subtree 08/07
    • Word Search 08/07
    • Pacific Atlantic Water Flow 08/08
    • Matrix Water Injection 08/10
    • Maximum Subtree 08/10
  • Dynamic Programming
    • 931. Minimum Falling Path Sum
    • Unique Binary Search Trees
  • Linked List
    • Reverse Linked List
    • Linked List Cycle
    • Swap Nodes in Pairs
    • Odd Even Linked List
    • Merge k Sorted Lists
    • Partition List
    • Palindrome Linked List
    • Reorder List
    • Linked List Cycle II
    • Delete Node in a Linked List
    • Reverse Nodes in k-Group
    • Rotate List
    • Reverse Linked List II
  • Arrays
    • 189. Rotate Array
    • 80. Remove Duplicates from Sorted Array II
    • 26. Remove Duplicates from Sorted Array
    • 628. Maximum Product of Three Numbers
    • 48. Rotate Image
    • 289. Game of Life
    • 334. Increasing Triplet Subsequence
    • 11. Container With Most Water
    • 122.Best Time to Buy and Sell Stock II
    • 274. H-Index
    • 134. Gas Station
    • 118. Pascal's Triangle
    • Sort Colors
    • Remove Element
    • Merge sorted array
    • First Missing Positive
  • Strings
    • 93. Restore IP Addresses
    • 71. Simplify Path
    • 43. Multiply Strings
    • 606. Construct String from Binary Tree
    • 917. Reverse Only Letters
    • 929.Unique Email Addresses
    • Valid Anagram
    • Compare Strings
    • Anagrams
    • Longest Common Prefix
    • Implement strStr()
    • String to Integer (atoi)
Powered by GitBook
On this page

Dynamic Programming

很有可能使用动态规划的情况：

  1. 求最大值最小值

  2. 判断是否可行

  3. 统计方案个数

不使用动态规划的情况：

  1. 求出所有具体的方案而非方案 个数

  2. 输入数据是一个 集合 而不是 序列

  3. 暴力算法的复杂度已经是多项式级别

    1. 动态规划擅长于优化指数级别复杂度（2^n,n!）到多项式级别复杂度(n^2,n^3)

    2. 不擅长优化n^3 到n^2

动态规划四要素 vs 递归 三要素

状态 state

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

方程 function

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

初始化 initialization

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

答案

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

递归三要素

定义(状态)

  1. 接受什么参数

  2. 做了什么事

  3. 返回什么值

拆解（方程）

  1. 何如将参数变小

出口(初始化)

  1. 什么时候可以直接return

初始化一个二维的动态规划数组时，先初始化第0行 第0列

PreviousMaximum Subtree 08/10Next931. Minimum Falling Path Sum

Last updated 6 years ago