w***y
发帖数: 6251 | 1 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
是什么问题?
1. BST optional BST??
2. COV
3. ILP
4. KS
5. LCS Longest Common Subsequences
6. LSP
7. MCM Matrix chain multiplication
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP Travelling salesman problem |
i**********e
发帖数: 1145 | 2 你上面的list我也没看懂。
补充一下我知道的一些经典的dp题：
LIS (longest increasing subsequence),O(n^2) DP, O(n log n) binary search加速
优化。
Edit distance.
Minimum path sum. 就是一个 MxN 矩阵，求从左上角到右下角的最小 sum.
当然还有经常问的 Unique paths, MxN 矩阵 从左上角到右下角总共有多少条路径。 |
w***y
发帖数: 6251 | 3 多谢啦!
我把这些题目还有 http://www.leetcode.com/category/dynamic-programming
都准备一下
【在 i**********e 的大作中提到】
: 你上面的list我也没看懂。
: 补充一下我知道的一些经典的dp题：
: LIS (longest increasing subsequence),O(n^2) DP, O(n log n) binary search加速
: 优化。
: Edit distance.
: Minimum path sum. 就是一个 MxN 矩阵，求从左上角到右下角的最小 sum.
: 当然还有经常问的 Unique paths, MxN 矩阵 从左上角到右下角总共有多少条路径。
|
p*****2
发帖数: 21240 | |
w***y
发帖数: 6251 | 5 应该不会太难, 不然写不完呐
不过我现在的问题是, 遇到题目很难往DP去想, 所以准备看看经典题目找找感觉hehe
【在 p*****2 的大作中提到】
: 我觉得面试遇到很难DP题的几率也不大。
|
p*****2
发帖数: 21240 | 6
恩。多做几道就可以了。
【在 w***y 的大作中提到】
: 应该不会太难, 不然写不完呐
: 不过我现在的问题是, 遇到题目很难往DP去想, 所以准备看看经典题目找找感觉hehe
|
J***e
发帖数: 50 | 7 COV (calculus of variation)
KS (knapsack problem)
【在 w***y 的大作中提到】
: 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
: 么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
: 是什么问题?
: 1. BST optional BST??
: 2. COV
: 3. ILP
: 4. KS
: 5. LCS Longest Common Subsequences
: 6. LSP
: 7. MCM Matrix chain multiplication
|
w****x
发帖数: 2483 | 8 贴一个我的分类:
Dynamic Programming
Write longest common sub sequence
Write longest common sub string
Find the length of the longest arithmetic progression sequence of a sorted
array
code a function that returns the nth fibnocci number
There is a square of n x n size which is comprised of n-square 1x1 squares.
Some of these 1x1 squares are colored. Find the biggest sub square which is
not colored. Also asked to extend it to find the biggest area rectangle.
Given a triangle like the following
3
4 6
1 5 0
How to find the largest sum from the top of the triangle to the one of the
nodes at the bottom.
Write a function that takes an array of five integers, each of which is
between 1 and 10, and returns the number of combinations of those integers
that sum to 15 |
l*********8
发帖数: 4642 | 9 3
4 6
1 5 0
这个三角形有什么规律？？
.
is
【在 w****x 的大作中提到】
: 贴一个我的分类:
: Dynamic Programming
: Write longest common sub sequence
: Write longest common sub string
: Find the length of the longest arithmetic progression sequence of a sorted
: array
: code a function that returns the nth fibnocci number
: There is a square of n x n size which is comprised of n-square 1x1 squares.
: Some of these 1x1 squares are colored. Find the biggest sub square which is
: not colored. Also asked to extend it to find the biggest area rectangle.
|
w****x
发帖数: 2483 | 10
木规律
【在 l*********8 的大作中提到】
: 3
: 4 6
: 1 5 0
: 这个三角形有什么规律？？
:
: .
: is
|
|
|
l*********8
发帖数: 4642 | 11 1. BST Optimal Binary Search Tree Problem
2. COV Optimal Covering problem
3. ILP integer linear programming
4. KS Knapsack Problem
5. LCS Longest Common Subsequences
6. LSP Longest Simple path Problem
7. MCM Matrix chain multiplication
8. ODP Optimal Distribution Problem
9. SCP Stagecoach Problem
10. SPA Shortest Path in a Acyclic graph
11. SPC Shortest Path in a Cyclic graph
12. TSP Travelling salesman problem
【在 w***y 的大作中提到】
: 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
: 么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
: 是什么问题?
: 1. BST optional BST??
: 2. COV
: 3. ILP
: 4. KS
: 5. LCS Longest Common Subsequences
: 6. LSP
: 7. MCM Matrix chain multiplication
|
p*****2
发帖数: 21240 | 12
哪里能找到这些原体呢？
【在 l*********8 的大作中提到】
: 1. BST Optimal Binary Search Tree Problem
: 2. COV Optimal Covering problem
: 3. ILP integer linear programming
: 4. KS Knapsack Problem
: 5. LCS Longest Common Subsequences
: 6. LSP Longest Simple path Problem
: 7. MCM Matrix chain multiplication
: 8. ODP Optimal Distribution Problem
: 9. SCP Stagecoach Problem
: 10. SPA Shortest Path in a Acyclic graph
|
i*******6
发帖数: 107 | 13 都是抢破头准备挤google的么...
除了google似乎别的公司都用不到dp.就算是google面到的概率也很低。 |
l*********8
发帖数: 4642 | 14 一本关于Dynamic programming的书
http://ishare.iask.sina.com.cn/f/9758339.html?from=isnom
不过里面的内容大多都不会考到吧。
【在 p*****2 的大作中提到】
:
: 哪里能找到这些原体呢？
|
p*****2
发帖数: 21240 | 15
DP面试的确不会太难，但是竞赛里的难题大多都是DP。你这本书都看了？
【在 l*********8 的大作中提到】
: 一本关于Dynamic programming的书
: http://ishare.iask.sina.com.cn/f/9758339.html?from=isnom
: 不过里面的内容大多都不会考到吧。
|
l*********8
发帖数: 4642 | 16 没有， 我哪有这么厉害：）
【在 p*****2 的大作中提到】
:
: DP面试的确不会太难，但是竞赛里的难题大多都是DP。你这本书都看了？
|
c********t
发帖数: 5706 | 17 mark
【在 w***y 的大作中提到】
: 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
: 么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
: 是什么问题?
: 1. BST optional BST??
: 2. COV
: 3. ILP
: 4. KS
: 5. LCS Longest Common Subsequences
: 6. LSP
: 7. MCM Matrix chain multiplication
|
h*******e
发帖数: 1377 | 18 据说做十道左右就可以了~~~但是手头有近100道的DP没有看.. |
