p*****2
发帖数: 21240 | 1 不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而... 阅读全帖 |
|
z******w
发帖数: 36 | 3 //用dp做的一个O(n^3)的解
import java.util.Scanner;
public class StreetTraversal {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] dis = new int[n][n];
for (int i = 0; i < n; i ++) {
dis[i] = new int[n];
for (int j = 0; j < n; j ++) {
dis[i][j] = sc.nextInt();
}
}
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i ++)
... 阅读全帖 |
|
M**********s
发帖数: 8 | 4 以下讨论都先设m==n，也就是资料为方阵，complexity写起来比较简单
如果非方阵的话设N=max(m, n)，big O还是对的
这题细节满多
我原本以为自己可以一次写对O(N^3)的解，但OJ发现有错
建议觉得自己能一次写对的人都试着自己写写看 http://soj.me/1767
四维DP的time complexity O(N^4)显然可以更好
如同前面说的三维可以达到time complexity O(N^3)
这题就是同时歸划两条左上角到右下角的不重疊路线，并最大化得分
要訣是每次同时考虑两条路线的同一步
设d为离左上角的曼哈頓距离
d=1第一步，考虑(0, 1), (1, 0)
只能选左线(0, 1)右线(1, 0)
d=2时一步，考虑(0, 2), (1, 1), (2, 0)
有左(0, 2)右(1, 1)、左(0, 2)右(2, 0)、左(1, 1)右(2, 0)三种选择
可以定义DP表dp[d][c1][c2]为
考虑左线进行到(r1, c1)，右线进行到(r2, c2)时的最大得分
r1 = d - c1, r2 = d - c2
这也是前面有人提到用对... 阅读全帖 |
|
p*****3
发帖数: 488 | 5 //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 6 写了一下。很麻烦。面试碰到肯定死了。
import java.io.*;
import java.util.*;
public class BalancedPartition
{
public static void main(String[] args)
{
new BalancedPartition().run();
}
PrintWriter out = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[] A = new int[]
{ 1, 2, 3, 4, 5, 6 };
balancedPar(A, 7);
out.close();
}
void balancedPar(int[] A, int k)
{
int n = A.length... 阅读全帖 |
|
s********u
发帖数: 1109 | 7 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
j*****y
发帖数: 1071 | 8 二爷可否帮我看看这个 dp 的写法是不是有什么地方值得优化的 :)
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s2.length();
if(s1.length() != n)
{
return false;
}
bool dp[n][n][n]; // dp[i][j][k] means the scrambility of substring
of length k + 1 starting at s1[i] and s2[j];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
for(int k = 0; k < n; ++k)
dp[i][j][k] = false;
for(in... 阅读全帖 |
|
发帖数: 1 | 9 题目如下：
String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。
----------------------------------------------------------------------
这里有解答，但是测试后发现不对（http://www.1point3acres.com/bbs/thread-145290-1-1.html）
结果测试sln.findMatches("aaaaaa", "a+a-") ，出来结果为0，不对
另外System.out.println(sln.fin... 阅读全帖 |
|
l**4
发帖数: 853 | 10 Update #1: VistaPrint估计不能用了
Update #2: 增加了travelocity
Update #3: 更加general的方法弄到DP（SHE+,PTF+,etc.）
做了点research，好好说说这个DP吧，希望对像我这样的新手有好处。目前第一次写这
个，有经验的老手请多多指教
1. Motivations
(1)前段时间由于shopper和CS上面热门GC的大量消失（BB,Mayce's等），不少人觉得似
乎这条路也越来越差了。
(2)最近版面上有人交易SHE+和PTF+什么的，（要价15刀？），我觉得这样一个版面应
该是大家分享信息的而不是闭塞资源。
(3)其实如何做这些deals，版面的精华区也都是有介绍的（不过就是老了点）。但是要
点还是那么几个吧。
2. 准备知识
2.1 What's DP
DP:DealPass. 初步了解可以参考精华区资源: http://www.mitbbs.com/bbsdoc4/life.faq/GiftCard/GiftCard/5
DP 有很多个不同的programs，每个program卖不同的GC。大部分的pr... 阅读全帖 |
|
p*****2
发帖数: 21240 | 11 def segmentString(s:String, dict:Set[String]):String={
val len=s.length()
val dp=Array.ofDim[Int](len+1,2)
(0 until len).reverse.foreach{i=>
(i+1 to len).foreach{j=>
if(dict.contains(s.substring(i,j)) &&
(j==len || dp(j)(0)>0) && (dp(i)(0)==0 || dp(j)(0)+1
{
dp(i)(0)=dp(j)(0)+1
dp(i)(1)=j
}
}
}
var ab=ArrayBuffer[String]()
if(dp(0)(0)>0)
{
var i=0
while(i!=len)
{
... 阅读全帖 |
|
c********p
发帖数: 1969 | 12 上代码，大家批斗！
public class Solution {
public boolean isMatch(String s, String p) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || p == null){
return false;
}
int slen = s.length();
int plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[0][0] = true;
for(int i = 1; i <= plen; i++){
if(p.charAt(i - 1) == '*'){
if( dp[... 阅读全帖 |
|
e********g
发帖数: 2524 | 13 thanks
做了点research，好好说说这个DP吧，希望对像我这样的新手有好处。目前第一次写这
个，有经验的老手请多多指教
1. Motivations
(1)前段时间由于shopper和CS上面热门GC的大量消失（BB,Mayce's等），不少人觉得似
乎这条路也越来越差了。
(2)最近版面上有人交易SHE+和PTF+什么的，（要价15刀？），我觉得这样一个版面应
该是大家分享信息的而不是闭塞资源。
(3)其实如何做这些deals，版面的精华区也都是有介绍的（不过就是老了点）。但是要
点还是那么几个吧。
2. 准备知识
2.1 What's DP
DP:DealPass. 初步了解可以参考精华区资源: http://www.mitbbs.com/bbsdoc4/life.faq/GiftCard/GiftCard/5
DP 有很多个不同的programs，每个program卖不同的GC。大部分的program现在都已经
不允许注册了，只有老会员了。因此这里只考虑到目前还在版面活跃的，可以注册的
programs：
Shopper Discounts&Rewards
CS: C... 阅读全帖 |
|
l**4
发帖数: 853 | 14 Update #1: VistaPrint网站估计已经失效了。
Update #2: 更加general的找到link的方法，（得自己摸索）
Update #3: travelocity下单弄到link的可行性得到了验证,包括PTF+和SHE+
Update #4: 增加了PTF+ 的GC信息，（感谢coarsening的帮助，发了2包子）
做了点research，好好说说这个DP吧，希望对像我这样的新手有好处。目前第一次写这
个，有经验的老手请多多指教
1. Motivations
(1)前段时间由于shopper和CS上面热门GC的大量消失（BB,Mayce's等），不少人觉得似
乎这条路也越来越差了。
(2)最近版面上有人交易SHE+和PTF+什么的，（要价15刀？），我觉得这样一个版面应
该是大家分享信息的而不是闭塞资源。
(3)其实如何做这些deals，版面的精华区也都是有介绍的（不过就是老了点）。但是要
点还是那么几个吧。
2. 准备知识
2.1 What's DP
DP:DealPass. 初步了解可以参考精华区资源: http://www.mitbbs.com/bbsd... 阅读全帖 |
|
l**4
发帖数: 853 | 15 Update #1: VistaPrint网站估计已经失效了。
Update #2: 更加general的找到link的方法，（得自己摸索）
Update #3: travelocity下单弄到link的可行性得到了验证,包括PTF+和SHE+
Update #4: 增加了PTF+ 的GC信息，（感谢coarsening的帮助，发了2包子）
做了点research，好好说说这个DP吧，希望对像我这样的新手有好处。目前第一次写这
个，有经验的老手请多多指教
1. Motivations
(1)前段时间由于shopper和CS上面热门GC的大量消失（BB,Mayce's等），不少人觉得似
乎这条路也越来越差了。
(2)最近版面上有人交易SHE+和PTF+什么的，（要价15刀？），我觉得这样一个版面应
该是大家分享信息的而不是闭塞资源。
(3)其实如何做这些deals，版面的精华区也都是有介绍的（不过就是老了点）。但是要
点还是那么几个吧。
2. 准备知识
2.1 What's DP
DP:DealPass. 初步了解可以参考精华区资源: http://www.mitbbs.com/bbsd... 阅读全帖 |
|
b*****n
发帖数: 482 | 16 想了个思路，不知道对不对：
1. 当前sum of dread大于当前怪物dread，可以直接过关
if dread[i+1] <= dp[i], dp[i+1] = dp[i]; total price no change.
2. 当前sum of dread小于当前怪物dread，怪物price为1，则进行收买，因为其性价比
最高。
if dread[i+1] > dp[i], price[i+1] = 1, dp[i+1] = dp[i] + dread[i+1]; total
price++.
3. 当前sum of dread小于当前怪物dread，怪物price为2, 则先寻找0~i中price为1的
还没有被pick的最大dread，如果bribe它后sum of dread大于当前怪物dread，则收买
之，total price加1；如果不存在这样的怪物，则收买当前怪物，total price加2。
if dread[i+1] > dp[i], price[i+1] = 2, dp[i+1] = dp[i] + {max(dread[k],
where k阅读全帖 |
|
w****3
发帖数: 110 | 17 是我想错了，dp的时候再加一层循环，最后return 20.复杂度似乎是n^3
其实和楼上几位的想法是一样的，先将切每段短的木料的cost算出来，每次新加一段的
时候，尝试第一刀切在这段之前的所有位置，切成两段以后的cost都已经知道了，所以
在这k个切法里找到最小的存下来即可。
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 1; i < a.size(); i++) {
dp[... 阅读全帖 |
|
m********6
发帖数: 58 | 18 I got asked this question by Facebook. The tricky part is permutation can
only be counted once. Here is my solution:
public int getCount(int[] partitions, int target)
{
int[][] dp = new int[target+1][partitions.length];
Arrays.fill(dp[0], 1);
for (int i = 1; i <= target; i++)
{
Arrays.fill(dp[i], -1);
}
return getCount(partitions, target, 0, dp);
}
public int getCount(int[] partitions, int target, int index, int[][] dp)
{
if (target < 0)
{
return 0;
}
if (dp[target][i... 阅读全帖 |
|
c***u
发帖数: 190 | 19 上回在Ebiz发贴说DP退了350的cash back 到Citi了(monthly Charging)，而不是退到
买GCs时候用的Chase Credit Card.当时觉的人品太好了，DP竟然会在两个月后退cash
back。昨天接到chase 的电话，告知chase竟然一直在跟DP斗争。Chase的说法是，要是
DP不refund， 就要take back 所有的money。DP说退不到Chase了，只能退到Citi。
CRS 问我是不是 要cancel dispute。
实际情况是，我Citi的卡因为seruity 问题，被reissue 了一张新卡。因为没有及时
update 信用卡，membership 被自动cancel了。跟DP argue 未果后dispute Chase。
chase 每回都给转到DP。后来，气不过，给Chase 写了一封信（从自己的chase
account）。质问chase 为什么不处理这个case。 信的内容已经不是纯粹的dispute，
矛头不是指向DP，而是chase了。说chase 不处理这个case回伤害customers 的心，没 |
|
p*****2
发帖数: 21240 | 20
如果能证明贪心work就用贪心。不过很多时候看经验和感觉了。用贪心需要很小心，用
错的时候不少。如果能用DP，肯定DP保险。DP得到的一定是最优，应该不会有贪心work
，DP不work。当然前提是可以用DP。有些时候很难用DP来解，或者即使用DP，速度还是
慢，达不到要求。这种情况要不是DP用的不对，要不题目就应该用贪心来解。 |
|
s******n
发帖数: 3946 | 21 这个题目能用DP的关键是每个数都大于等于0：
总和为sum
A(i,Y) 表示前i项选任意个之和小于Y且与Y最接近的差。
所以我们要求：A(N, sum/2)
递推:
A(i, Y) = min(A(i-1, Y), A(i-1, Y-a[i]))
代码
============================================
dp[N][SUM/2];
for (int i=1; i
for (int j=0; j
dp[i][j]=MAX_INT;
for (int i=0; i
int calculate(int i, int sum)
{
if (dp[i,sum]!=MAX_INT) return dp[i,sum];
assert(i>0);
int solution1 = calculate(i-1, sum);
int solution2 = MAX_INT;
if (Y>a[i]) solution2 = calculate(i... 阅读全帖 |
|
p*****2
发帖数: 21240 | 22 然后再写bottomup的就容易了。
int bottomup(int[] arr, int n)
{
int m = arr.length;
dp = new int[2][n + 1];
dp[0][0] = 1;
dp[1][0] = 1;
for (int j = 1; j <= n; j++)
{
if (j % arr[0] == 0)
dp[0][j] = 1;
else
dp[0][j] = 0;
}
for (int i = 1; i < m; i++)
{
int curr = i % 2;
int prev = (i - 1) % 2;
for (int j = 1; j <= n; j++)
{
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 23 感觉罗嗦不少，你按照我的java代码改改试试？
public boolean isScramble(String s1, String s2)
{
int n=s1.length();
boolean[][][] dp=new boolean[n][n][n+1];
for(int i=n-1; i>=0; i--)
for(int j=n-1; j>=0; j--)
for(int k=1; k<=n-Math.max(i,j);k++)
{
if(s1.substring(i,i+k).equals(s2.substring(j,j+k)))
dp[i][j][k]=true;
else
{
for(in... 阅读全帖 |
|
w***o
发帖数: 109 | 24 这样行不行？只能找到最少的个数，加个数组，稍改一下就能找到如何分割。
int n = s.length();
int[] dp = new int[n+1];
Arrays.fill(dp, 1000000);
dp[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = i-1; j >= 0; j--) {
if(dict.contains(s.substring(j, i)))
dp[i] = Math.min(dp[i], dp[j]+1);
}
}
if(dp[n] > n)
System.out.println(“Not valid”);
else
System.out.println(“” + dp[n]); |
|
J****3
发帖数: 427 | 25 DP 方程 assume dp[i][j] means number of distinct subsequence number of S[0,i
] and T[0,j]
then for each character, two cases: 1. S[i] != T[j]: dp[i][j] = dp[i-1][j].
2. S[i] == T[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
我们可以依据方程写出DP， 普通是2维，lz给的是一维滚动数组， 遍历方向相反可以
防止重复计算 |
|
q******n
发帖数: 35 | 26 首先，得到每一块木头的长度，例如，楼主的例子：
L[0] = 2, L[1] = 2, L[2] = 3, L[3] = 3
然后，定义DP[i][j]为从第i块木头的左边开始切，切j块木头的最优解。
DP[i][1] = 0
DP[i][2] = L[i] + L[i+1]
DP[i][3] = L[i] + L[i+1] + L[i+2] + min (DP[i][1]+DP[i+1][2],DP[i][2]+DP[i+2
][1])
以此类推就可以了 |
|
c*****m
发帖数: 271 | 27 感觉是wildcard matching的扩展，a+b+c-转换成*aa*bb*cccc，然后dp的过程中记录次
数，写的python代码如下，测试用例过了：
def match(s, p):
#invalid input
if len(p) % 2 != 0:
return -1
#reconstruct p
temp = ''
i = 0
while i < len(p):
#add '*' first
temp += '*'
#add char pattern
if p[i+1] == '+':
temp += p[i] * 2
else:
#p[i+1] == '-'
temp += p[i] * 4
#iterate to next char
i += 2
p = temp
print p
#... 阅读全帖 |
|
l****u
发帖数: 1764 | 28 想到一个用dp的方法，如果slices数量比较小（小于30），可以用一个整形数组表示
sub problem，比如dp[111111111]表示完整pizza（9个slices）的最优解，dp[
111110001]表示第2个slice被拿掉的最优解，dp[100010001]表示第2个slice和第6个
slice被拿掉的最优解
数组下标是二进制表示，最多可以表示30个slice的问题
如果要超过30个（一个pizza切30块也差不多了吧？），那可能就得用string做下标，
存在hashmap里面了
base case 是只剩3个slice的时候(可以用位操作判断这个条件)，dp[0.a.b.c.0] =
max(dp[0.a.0],dp[0.b.0],dp[0.c.0]) |
|
b***l
发帖数: 196 | 29 ☆─────────────────────────────────────☆
caohu (愤怒的Tiger) 于 (Sat Sep 29 10:17:06 2007) 提到:
上回在Ebiz发贴说DP退了350的cash back 到Citi了(monthly Charging)，而不是退到
买GCs时候用的Chase Credit Card.当时觉的人品太好了，DP竟然会在两个月后退cash
back。昨天接到chase 的电话，告知chase竟然一直在跟DP斗争。Chase的说法是，要是
DP不refund， 就要take back 所有的money。DP说退不到Chase了，只能退到Citi。
CRS 问我是不是 要cancel dispute。
实际情况是，我Citi的卡因为seruity 问题，被reissue 了一张新卡。因为没有及时
update 信用卡，membership 被自动cancel了。跟DP argue 未果后dispute Chase。
chase 每回都给转到DP。后来，气不过，给Chase 写了一封信（从自己的chase
account） |
|
g**********y
发帖数: 14569 | 30 a = [1, 2, 3, 4, 5], sum = 15
dp[] = new int[16]
initialize dp[0] = 1
依次考虑a[i], 计算结果：
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0
1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1
最后，count = 1
Java code ->
private void count(int[] a, int sum) {
int[] dp = new int[sum+1];
dp[0] = 1;
for (int i=0; i
for (int j=sum-a[i]; j>=0; j--) {
dp[j+a[i]] += dp[j];
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 31 写了一个topdown dp的。
import java.io.*;
import java.util.*;
public class Coin
{
public static void main(String[] args)
{
new Coin().run();
}
PrintWriter out = null;
int[][] dp = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[] arr = new int[]
{ 25, 10, 5, 1 };
int n = 11;
dp = new int[arr.length][n + 1];
for (int i = 0; i < arr.length; i++)
Arrays.fil... 阅读全帖 |
|
p*****2
发帖数: 21240 | 32 感觉dp[i][j] 是 A在i城市，B在j城市的情况
最后返回dp[0][0]
如果i+1
如果i+1==j的话， dp[i][j]=min(dp[i+2][j]+distance(i,i+2), dp[i][j+1]+
distance(j,j+1))
j |
|
e***s
发帖数: 799 | 33 下面是我想到的，不知道对不对。
public static String segmentStringDP(String s, Set dict){
if(dict.contains(s)) return s;
int len = s.length();
int[] dp = new int[len];
for(int i = 0; i < len; i++)
{
for(int j = i; j < len; j++)
{
if(dict.contains(s.substring(i, j + 1)))
{
if(i == 0 || dp[i - 1] > 0)
dp[j] = Math.max(dp[j], j - i + 1);
... 阅读全帖 |
|
s*****i
发帖数: 32 | 34 照片可以贴在跨越边界的地方，比如跨越dp[m-a][b] 和 dp[m][n-b]交接的那条线。
子问题是一个六边形，这个六边形问题不是简单的max(dp[m-a][b] + dp[m][n-b], dp[
m-a][n] + dp[a, n-b])就能解决的。也就是说子问题跟原问题已经不一样了。
发信人: gloomyturkey (一只郁闷的火鸡), 信区: JobHunting
标 题: Re: 求问G面试题，非普通的DP
发信站: BBS 未名空间站 (Wed Dec 25 16:18:03 2013, 美东)
没有什么问题啊，看不出来漏了什么解。USACO里有道题就是那样设计的 |
|
w****3
发帖数: 110 | 35 i表示计算的长度，j表示最后一切的位置，0放入index0，L放入最后一个index为编程
方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 2; i < a.size(); i++) {
dp[2][i] = a.get(i) - a.get(i-2);
}... 阅读全帖 |
|
f********0
发帖数: 498 | 36 版主悬赏大包子写一下dispute过程，诱惑大大的，虽然还没见过大包子长什么模样。
希望对以后credit card dispute DP的人有用。
八月份AMEX CC被suspend了几天，恰巧DP这个时候charge月费，这丫当天就cut了我的
program，也不再charge一次试试。$600 的credit在9月初就没有退回，理由是
membership is not active when requesting credit。没有其他违反DP规定。
9月初打电话给DP argue未果。今天又打DP电话，VPR愿意转到tech department处理，
BM立马拒绝我，没有余地。于是决定两家一起dispute算了，不陪DP玩了。
打AMEX客服电话，告诉csr我要dispute VPR,BM 8月份charge我三笔费用的20%。询问原
因，说这两个公司应当每月credit我上月消费的20%。csr可以看到我帐号上前几个月都
有20% credit来自这VPR和BM，也就没有多问。又问我有没有凭证应该退我20%，告诉他
有packing slip，写了有20% credi |
|
w****x
发帖数: 2483 | 37 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
得学到蛮多的，分享一下。
以前写过一个很挫的DP版本：
int GetEditDist(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2];
bool bFound = false;
for (int i = 0; i < nLen2; i++)
{
if (str2[i] == str1[0])
bFound = true;
rec[i] = bFound ? i : i+1;
}
bFound = (str2[0] == str1[0]); //(str2[0] == str1[0]) not false
for (int i = 1; i < nLe... 阅读全帖 |
|
|
r***t
发帖数: 125 | 39 因为最近和DP打交道很多，加上所有的DP program都死光了，所以来写一些基本的原则
和体会给同学们，希望对大家有所帮助
1： 什么是cancel?
A: Cancel，就是你用你的帐号和zip登录以后，无法看见通常的program字样，而是一
个灰灰的框。写着“due to condition & terms” blah blah blah. 通常你会收到一
封email/mail，有时候什么也没有。
2： Cancel后有没有可能恢复DP帐号？
A： Unfortunately， never ever. （不管是谁的错，看起来dp系统里就没有恢复帐号
的选项）
3： 为什么会cancel？
A； 被cancel有几个原因：
1）你自己cancel的（不管是真想还是误操作）
2)由于DP无法charge你用来付月费/年费的钱，这种情况在ONe time use 的CC
（如citi的）经常出现。
3)你有multiple membership (同一个人有多个地址/或者同一个地址有多个人)
这里有一种情况需要阐明：就是有的同学本身 |
|
e*******u
发帖数: 147 | 40 其实是2组各3个
PTF+ PTF AHR+
同名 不同地址 CC 电话号码
干过的坏事
1. 直接寄到买家地址（干过不下50次）
2. 某买家声称没有收到一次卡，打电话Argue过，后来卡收到了，但是那个月的re
fund没收到，继续打电话argue
3. 曾经在很短的时间，密集的place了很多order寄到同一地址（上个月也干过，没
有出现任何问题）
心得体会
1. 估计密集place 同一program的order会出事（如两个AHR+），DP寄卡的时候认真
一点的人总有机会发现人名一样。我之前搞过那么多次也没出事，所以我觉得多个
地址，寄到同一个人那里，只要小心点，应该问题不大
2. 打电话也许是个导火索，导致DP会调查，别有事没事的找DP CS练英语
3. 没了也好，DP这东西，小搞宜情，大搞伤身，珍惜生命，远离DP。
斑竹毛一个吧 |
|
a******n
发帖数: 4290 | 41 理由说我duplicate membership with PTF.
大概半年前，dp突然莫名其妙得自动给我们发了一个PTF的membership ID。
因为手头已经有一个了，我赶紧打电话说，我们没有order这个id,希望不要被认定为
duplicate membership. dp的人说，马上咳嗽，不会认定我们家是重复申请ptf.
这都半年过去了，突然不让我登陆ptf。打电话给csr,dp的人说我的membership is
fine,没有问题。过了大概1周，dp的正式email通知到了，说我duplicate membership
with ptf.
我又打电话过去，他们说no matter for 什么原因，反正就是取消membership了，等收
到正式书面通知，我可以根据书面通知做response。
我的ptf反正也早已经挖掘的差不多了，咳嗽了也就罢了。
他们不会把我其他的program也给咳嗽了吧？我也不希望上黑名单的说，以后还得跟dp
玩啊。
事情好奇怪啊？ 请指教～～
我老革命遇到新问题了。 |
|
Z*****Z
发帖数: 723 | 42 把所有硬币放在一个数组c里面。然后函数F[i,j]代表用前i个硬币摆出value j的摆法。
初始F[*,*] = 0
然后F[i,j] = sum(F[i-1, j - k * c[i]]) 0 <= k <= j/c[i]
实现起来可以用背包九讲里面第二讲的方法：
F[i,j] = F[i, j - c[i]] + F[i-1, j]
代码：
package common.knapsack;
public class Complete {
public static void main(String[] args) {
int[] in = {1, 5, 10, 25};
System.out.println(howMany(in, 11));
}
//How many ways to pack
public static int howMany(int[] arr, int n){
... 阅读全帖 |
|
n*******w
发帖数: 687 | 43 如果像这么定义 .和* 可以用DP。
很多定义是不能DP的，比如
*表示匹配前一个字符任意次
+表示匹配前一个字符至少一次
a-z表示匹配a-z之间任意字符
。。。
有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
身没有dependency。
另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
3道coding，至少也得2道。时间还是紧张了。当然牛人除外。
( |
|
j******2
发帖数: 362 | 44 一直以为DP就是store了之前结果的recursion。但是看到150第五版里，把18.12（最大
和的submatrix）归为DP&recursion（在9章末提到）。18.12显然没有递归，是在
iteratively利用之前的结果。所以是否DP就是recursion or iteration with stored
results?
但是18.11（最大的黑边square）里面，第二种方法把右、下的黑像素个数存储起来的
过程，跟18.12非常相似啊，iteratively using previous results，但是却没有算成
DP。
所以DP的特征究竟是什么？ |
|
j******2
发帖数: 362 | 45 想着想着又有点糊涂了。DP的精髓究竟是1.存储先前结果，还是2.利用最优子问题解决
现有最优问题？
如CLRS及devilphoenix所说，DP的关键2.，但是这样的话，经典DP fibonacci有什么最
优选择可言啊？不就是存储先前结果吗？
18.11（最小黑边框）的preprocess也很像fibonacci的情况，一步步存结果，累加，没
有选择出现。
如果fibonacci算DP，那很多iteration和recursion凡是利用了前面结果的是不是都要
算DP啊？比如string permutation. |
|
l*****a
发帖数: 14598 | 46 62 Unique Paths 2 3
array
dp
63 Unique Paths II 3 3
array
dp
95 Unique Binary Search Trees II 4 1
tree
dp
dfs
96 Unique Binary Search Trees 3 1
tree
dp
这几个都归为DP了？ |
|
r**********o
发帖数: 50 | 47 不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
就算用取2种分法的max，还是有漏掉一些解吧？
dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
dp[m-a][n] + dp[a, n-b]);
|
|
b***e
发帖数: 1419 | 48 以每一条逆对角线作为一步来进行dp。每条逆对角线上讨论任意两个点的所有情况。不
要想成是一来一回，想成是两条上下互不相交的路线齐头并进，逐步穿越每一条逆对角
线。DP函数的参数有三个：逆对角线的index，其上两点的两个index。所以应该是三维
DP，不是四维DP。
DP |
|
d********i
发帖数: 582 | 49 代码已贴。
public static int rodCutting(int[] price, int RodLength) {
int dp[] = new int[RodLength + 1];
for (int i = 1; i <= RodLength; i++) {
for (int j = 0; j < price.length; j++) {
if (j < i) {
dp[i] = Math.max(dp[i], dp[j] + price[i - 1 - j]);
}
}
}
return dp[RodLength];
} |
|
c********g
发帖数: 15629 | 50 DP虽然寄来一些“收据”，但那上面根本就没有卡号，谁也无法证明自己的DP卡确实是
从DP来的。比如我现在想卖一张Blockbuster的卡，我根本就不知道是从DP，EPG，还是
FFR来的，虽然我知道就是从这三个program里的某一个来的。我也没法提供准确的收据
呀。
还有必须一手的说法，比如某大牛，手下有一帮小弟专门供卡，大牛什么卡都收，然后
集中起来出售或者交换，这个算一手的还是二手的？他说是一手的，谁也没法证明不是
一手的啊。这个规定跟没有一样。
“不建议进行货币交易”，这不是自欺欺人嘛，GC交易就是货真价实的货币交易。
1000伪币值10美元吧，这不是卖官鬻爵嘛。还不如谁发个广告，上交20伪币呢，算
listing fee吧，顶一次10伪币，欢迎来顶自己的帖子。这样来收伪币既公平还能收得
多。老邢也可以开动印钞机了:-)
“明码标价”，那有价格以后再加上best offer，OBO，PM算不算明码标价呢？
ebay不道德交易可以去ebiz，staples coupon可以去网上直接买，去ebiz卖，问题也不
大。
胡乱想到一些，就随便说说。我有自己的交易原则，在这里交易过一两 |
|
