@w1024020103 2017-05-24T07:05:02.000000Z 字数 376 阅读 1028

Lecture 31: Dynamic Programming

CS61B

Shortest Paths in a DAG

DAG directed acyclic graph

image_1bgsjkn7412i5mt0h691p00kaq9.png-77.7kB

SPTs on Directed Acyclic Graphs

image_1bgsjm0bp3rk15q6a2ktdloqcm.png-80.3kB

Demo

Runtime Analysis

image_1bgsk1mla1hhc12tp73hh7vpr413.png-123.7kB

Dynamic Programming

Definition

image_1bgsk6dvu1vln1nib14lrqs21php1g.png-110.9kB

Steps

image_1bgsk76bt134srnjh8p19a31bhp1t.png-95.9kB

Longest Increasing Subsequence (LIS)

LLIS

image_1bgskbbietnl6suckt1ursit12a.png-75.5kB

LLIS and DAG

image_1bgskdchoi187pqmm5bdbuji2n.png-87.7kB

DAG Longest Path Algorithm

image_1bgskeaaf1q7rf6j563jk5pqa34.png-76.6kB

Using a negative weight to find the longest path

image_1bgski7cg1rtg13jjbu919ceikn3h.png-108.7kB

Runtime

image_1bgskk43b14u72mg1bg71uj8vnt3u.png-98.8kB

Summary

image_1bgsklbas1t5k1d9rh5c1eu3m8r4b.png-125.8kB

LIS Using Dynamic Programming

Examples of LLIS subproblems

image_1bgskq3hu16edmqt1mi51pm6a14o.png-115.2kB

image_1bgskr1pe26lbs21u291u6s18a455.png-79.2kB

Dynamic programming solution for LLIS problem

image_1bgsku5q71htl1ab11ioc1v1ergd5i.png-114.3kB

Summary

image_1bgsl03qutj4sih1audhfn1ib55v.png-166.9kB
image_1bgsl0cu4gt1a0q1c1lfud1rnt6c.png-78.8kB

- - 17spring 1
  - Static vs Instance Methods
- - Algorithm 1
  - Interview Questions
- - Arguments 1
  - How to use Command-Line Arguments
- - Array 4
  - Move Zeroes
  - 二刷Maximum Subarray
  - Median of two Sorted Arrays
  - Subarray Sum Closest
- - BinarySearch 4
  - Divide Two Integers
  - K Closest Numbers In Sorted Array
  - Drop Eggs
  - Total Occurrence of Target
- - BinaryTree 3
  - Binary Tree Longest Consecutive Sequence II
  - Binary Tree Path Sum II
  - Lowest Common Ancestor II
- - CS61B 64
  - How to write recursive method (recursion)
  - Project 3: Bear Maps, version 2.0
  - Study Guide : Sorting I (Basic Sorts)
  - Lecture 32: Sorting I
  - Lecture 31: Dynamic Programming
  - Homework 4: 8 Puzzle
  - lab11 Graphs
  - Discussion 11
  - Lecture 30: Graphs IV: Minimum Spanning Trees
  - Shortest Paths and Dijkstra's Algorithm
  - Lecture 29: DFS vs. BFS, Shortest Paths
  - Graph Traversals Study Guide
  - Lec 28 Graph Traversals
  - Lab 10: Priority Queues
  - Lecture 26: Graphs
  - Homework 3: Hashing
  - Lecture 25: Advanced Trees
  - Heaps and Priority Queues Study Guide
  - Homework 2: Disjoint Sets and Percolation
  - Lab 9: Hash Maps
  - Hashing Study Guide
  - Lecture 23: Hashing
  - java.lang.ClassNotFoundException
  - Lab 8: BSTs and Asymptotics
  - Lecture 22: Balanced Search Trees
  - Balanced BST Study Guide
  - Lecture 21: Binary Search Trees
  - Disjoint Sets Study Guide
  - Lecture 20: Disjoint Sets
  - discussion7
  - 关于Big O, Big Theta, Big Omega和Best Case, Worst Case, Average Case
  - lec 18 Asymptotics II
  - lec 17 Asymptotics I
  - Homework 1: Packages, Interfaces, Generics, Exceptions, Iteration
  - discussion6 2 Breaking the System
  - discussion 6 Design a Parking Lot ADT
  - Discussion 6 Immutable Rocks
  - Lec16 Exceptions, Access Control, Objects
  - Proj2与SimpleDB的转换
  - Proj2 Your Task
  - Proj2 2.7. Query Parser and Contest
  - Proj2 2.4. Insertion and deletion
  - Proj2 2.3. HeapFile Mutability
  - Proj2 2.6Query walkthrough
  - Proj2 2.1 Filter and Join
  - Proj2 A simple query
  - Proj2 Operators
  - Proj2 HeapFile
  - Proj2 BufferPool
  - Proj2 Catalog.java
  - CS61B Discussion 6 Immutable
  - HashMap
  - Proj2 RowDesc.java Row.java
  - Lab 5 Notes
  - discussion4 notes
  - Proj1B Notes
  - Lab 3 Notes
  - Lab 2 Notes
  - CS61B Proj1A notes
  - week2 2.3 2.4 notes
  - 在Sublime Text 3上编译和运行java程序
  - CS61B Lab 1
  - git bash 使用 sublime_text 为默认编辑器
  - Static vs Instance Methods
- - Command-Line 1
  - How to use Command-Line Arguments
- - Comparator 1
  - K Closest Numbers In Sorted Array
- - Coursera 1
  - Interview Questions
- - DFS 1
  - Binary Tree Path Sum II
- - DataStructure 3
  - Rehashing
  - 哈希表Hash
  - Hash Function
- - DynamicProgramming 1
  - Knight Shortest Path II
- - Eclipse 1
  - Cannot make a static reference to the non-static field solved
- - Exceptions 1
  - Proj2 RowDesc.java Row.java
- - IntelliJ 2
  - java.lang.ClassNotFoundException
  - IntelliJ新建一个类的快捷键
- - Interview 1
  - Interview Questions
- - Iterable 1
  - How to actually use Iterable and Iterator?
- - Iterator 1
  - How to actually use Iterable and Iterator?
- - Java 5
  - How to use Command-Line Arguments
  - equals方法
  - How to actually use Iterable and Iterator?
  - Cannot make a static reference to the non-static field solved
  - Interview Questions
- - Jiuzhang 1
  - Chapter 3 Binary Tree Divide Conquer
- - JoshHug 1
  - week2 2.2 notes
- - LAC 1
  - Lowest Common Ancestor II
- - LeetCode 31
  - Binary Tree Longest Consecutive Sequence II
  - Search a 2D Matrix II
  - Divide Two Integers
  - K Closest Numbers In Sorted Array
  - Drop Eggs
  - Total Occurrence of Target
  - Knight Shortest Path II
  - Rehashing
  - Hash Function
  - Move Zeroes
  - Window Sum
  - Merge Two Sorted Arrays
  - 二刷Maximum Subarray
  - Median of two Sorted Arrays
  - Subarray Sum Closest
  - Reverse Linked List II二刷
  - Merge Two Sorted Lists
  - Reverse Linked List II
  - Combination Sum
  - Subsets II
  - Subsets
  - Number of Islands
  - Search Graph Node
  - Clone Graph
  - Binary Tree Serialization
  - Smallest Rectangle Enclosing Black Pixels
  - Binary Tree Level Order Traversal
  - Search in a Big Sorted Array
  - Maximum Number in Mountain Sequence
  - Search a 2D Matrix
  - Implement strStr()
- - LinkedList 3
  - Reverse Linked List II二刷
  - Merge Two Sorted Lists
  - Insert into a Cyclic Sorted List
- - LintCode 34
  - Binary Tree Longest Consecutive Sequence II
  - Binary Tree Path Sum II
  - Lowest Common Ancestor II
  - Search a 2D Matrix II
  - Divide Two Integers
  - K Closest Numbers In Sorted Array
  - Drop Eggs
  - Total Occurrence of Target
  - Knight Shortest Path II
  - Rehashing
  - Hash Function
  - Move Zeroes
  - Window Sum
  - Merge Two Sorted Arrays
  - 二刷Maximum Subarray
  - Median of two Sorted Arrays
  - Subarray Sum Closest
  - Reverse Linked List II二刷
  - Merge Two Sorted Lists
  - Reverse Linked List II
  - Insert into a Cyclic Sorted List
  - Combination Sum
  - Subsets II
  - Subsets
  - Number of Islands
  - Topological Sorting
  - Search Graph Node
  - Clone Graph
  - Binary Tree Serialization
  - Smallest Rectangle Enclosing Black Pixels
  - Binary Tree Level Order Traversal
  - Search in a Big Sorted Array
  - Maximum Number in Mountain Sequence
  - Search a 2D Matrix
- - MVC 1
  - Spring MVC 项目所用git 操作记录
- - Mac 1
  - Launchpad上删不掉的图标
- - Spring 1
  - Spring MVC 项目所用git 操作记录
- - Sublime 1
  - Sublime Text如何删除多行首字母删除行号
- - Text 1
  - Sublime Text如何删除多行首字母删除行号
- - TwoPointers 4
  - Search a 2D Matrix II
  - K Closest Numbers In Sorted Array
  - Move Zeroes
  - Window Sum
- - UCBerkeley 8
  - Proj2 RowDesc.java Row.java
  - Lab 5 Notes
  - discussion4 notes
  - Proj1B Notes
  - Lab 3 Notes
  - Lab 2 Notes
  - CS61B Proj1A notes
  - week2 2.3 2.4 notes
- - Unit 1
  - Proj2 RowDesc.java Row.java
- - algorithem 2
  - A* search algorithm.
  - labeled break statement
- - algorithm 4
  - KdTree.java使用了未经检查或不安全的操作
  - java.lang.ArrayIndexOutOfBoundsException: 3
  - Priority Queue exercises
  - How to find time complexity of an algorithm
- - array 1
  - Merge Two Sorted Arrays
- - assignment 1
  - labeled break statement
- - bash 1
  - Git push error
- - binarytree 1
  - Traverse a Binary Tree
- - bitoperation 1
  - Divide Two Integers
- - bittiger 3
  - Bittiger Lesson 4
  - Bittiger Lesson3
  - cs106 bittiger lesson1
- - coursera 5
  - KdTree.java使用了未经检查或不安全的操作
  - A* search algorithm.
  - labeled break statement
  - java.lang.ArrayIndexOutOfBoundsException: 3
  - Priority Queue exercises
- - cs 2
  - Bittiger CS106 lesson2
  - cs106 bittiger lesson1
- - cs61b 3
  - week2 2.2 notes
  - Test Your Understanding of the GRoE
  - Git fatal: refusing to merge unrelated histories
- - data 2
  - Bittiger Lesson 4
  - Bittiger CS106 lesson2
- - datastructure 1
  - HashMap
- - equals 1
  - equals方法
- - fundanmental 1
  - Bittiger Lesson3
- - git 4
  - Spring MVC 项目所用git 操作记录
  - Git push error
  - Git fatal: refusing to merge unrelated histories
  - git bash 使用 sublime_text 为默认编辑器
- - github 2
  - Git push error
  - Git fatal: refusing to merge unrelated histories
- - inorder 1
  - Traverse a Binary Tree
- - iterable 1
  - What is the difference between iterator and iterable and how to use them?
- - iterator 1
  - What is the difference between iterator and iterable and how to use them?
- - java 10
  - Spring MVC 项目所用git 操作记录
  - CS61B Proj1A notes
  - 在Sublime Text 3上编译和运行java程序
  - Bittiger Lesson 4
  - Bittiger Lesson3
  - labeled break statement
  - java.lang.ArrayIndexOutOfBoundsException: 3
  - Java 自加自减前缀后缀区别
  - 打印对象和toString方法
  - What is the difference between iterator and iterable and how to use them?
- - java关键字 1
  - Java this关键字详解
- - java基础 1
  - 打印对象和toString方法
- - jianshu 1
  - What is the difference between iterator and iterable and how to use them?
- - language 1
  - Java 自加自减前缀后缀区别
- - mac 1
  - Mac 键盘图标与对应快捷键按键标志
- - macbook 1
  - Launchpad上删不掉的图标
- - non-static 1
  - Cannot make a static reference to the non-static field solved
- - postorder 1
  - Traverse a Binary Tree
- - preorder 1
  - Traverse a Binary Tree
- - princeton 2
  - KdTree.java使用了未经检查或不安全的操作
  - A* search algorithm.
- - pro 1
  - Launchpad上删不掉的图标
- - programming 1
  - Java 自加自减前缀后缀区别
- - push 1
  - Git push error
- - reference 1
  - Cannot make a static reference to the non-static field solved
- - shortcut 1
  - IntelliJ新建一个类的快捷键
- - stackoverflow 1
  - What is the difference between iterator and iterable and how to use them?
- - static 1
  - Cannot make a static reference to the non-static field solved
- - structure 2
  - Bittiger Lesson 4
  - Bittiger CS106 lesson2
- - sublime_text 1
  - git bash 使用 sublime_text 为默认编辑器
- - sublime_text3 1
  - 在Sublime Text 3上编译和运行java程序
- - test 1
  - Proj2 RowDesc.java Row.java
- - this 1
  - Java this关键字详解
- - timecomplexity 1
  - How to find time complexity of an algorithm
- - toString 1
  - 打印对象和toString方法
- - treetraversal 1
  - Traverse a Binary Tree
- - ucberkeley 1
  - week2 2.2 notes
- - week4 1
  - A* search algorithm.
- - 快捷键 1
  - IntelliJ新建一个类的快捷键
- - 搜索技巧 1
  - Search Tips 搜索技巧
- - 用法 1
  - Java this关键字详解
- - 电脑问题 1
  - Win7 关机自动重启
- - 算法 1
  - Interview Questions
- - 系统 1
  - Win7 关机自动重启
- - 未分类 2
  - Lecture 24: Priority Queues and Heaps
  - git push error "Integrate the remote changes..."
- 以下【标签】将用于标记这篇文稿：

添加新批注

在作者公开此批注前，只有你和作者可见。

私有
公开
删除

回复批注

Lecture 31: Dynamic Programming

Shortest Paths in a DAG

DAG directed acyclic graph

SPTs on Directed Acyclic Graphs

Runtime Analysis

Dynamic Programming

Definition

Steps

Longest Increasing Subsequence (LIS)

LLIS

LLIS and DAG

DAG Longest Path Algorithm

Using a negative weight to find the longest path

Runtime

Summary

LIS Using Dynamic Programming

Examples of LLIS subproblems

Dynamic programming solution for LLIS problem

Summary

内容目录