详谈如何最大化利用career fair

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 322|回复: 5
收起左侧

[动态规划] 如何判断dp array size应该是len 还是 len +1

[复制链接] |试试Instant~
我的人缘3
pxu 发表于 2018-7-12 05:53:43 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  67% (307)
 
 
32% (149)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
本帖最后由 nunuh89 于 2018-7-14 12:56 编辑



我在做动态规划的时候,不是很清楚什么时候dp的size应该是A.length 还是A.length+1.比如是说下面的Jump Game,好像就用 boolean dp[] = new boolean[len]。
*     * @param A: A list of integers     * @return: A boolean     */
    public boolean canJump(int[] A) {        // write your code here        
if( A == null || A.length == 0){
            return true;        
}               
int len = A.length;        
boolean dp[] = new boolean[len];        
dp[0] = true;               
for(int i = 1; i < len; i++){            
for(int j = 0; j < i; j++){               
dp = dp[j] && (A[j] >= (i-j));               
if(dp){                    break;                }            
}        
}               
return dp[len-1];        

但是,在其它题目里,比如说[color=rgba(0, 0, 0, 0.85)]Decode Ways[color=rgba(0, 0, 0, 0.85)] - [color=rgba(0, 0, 0, 0.85)]Java,就用到len+1。 请教大神们,看能否说明一下,什么时候用len,什么时候用len+1,谢谢!
ublic class Solution {    /**     * @param s: a string,  encoded message     * @return: an integer, the number of ways decoding     */    public int numDecodings(String s) {

        // write your code here               
if(s == null || s.isEmpty()) return 0;               
int dp[] = new int[s.length()+1];        
dp[0] = 1;        
dp[1] = s.charAt(0)=='0'?0: 1;               
for(int i = 2; i < s.length()+1; i++){            
int first = Integer.valueOf(s.substring(i-1,i));            
int second = Integer.valueOf(s.substring(i-2,i));                        
if(first > 0 && first <=9){                dp += dp[i-1];            }                        
if(second >= 10 && second <=26){                dp += dp[i-2];            }        
}               
return dp[s.length()];                    
}
}






上一篇:【自我监督贴】暑假刷题刷课
下一篇:谈谈面试官在面试coding题目时的考察终点与心理活动, 求大米
我的人缘3
 楼主| pxu 发表于 2018-7-12 05:58:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  67% (307)
 
 
32% (149)  踩
格式好像有很大问题,还不让编辑:(. 不过问题很简单,什么时候dp的size用输入数组length, 什么时候应该用length+1.谢谢指教。
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
monsoonle 发表于 2018-7-12 09:02:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
这取决于你dp[n] 是怎么定义的。。。。用length + 1只是因为需要用到dp[length], 不这样初始化就越界了

评分

参与人数 1大米 +3 收起 理由
pxu + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-7-12 09:19:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (572)
 
 
20% (152)  踩

定义dp array的时候要弄清楚, 是 up to ith position, inclusive 还是 exclusive.
几个经典例子

1) coin change [322]
定义 f[i] 为 minimum number of ways to decompose change [i]
所以按你的说法显然是要int[] f = new int[amount + 1]的.

2) climbing stairs [70]
定义 f[i] =  total number of ways to climb up to stair [i]
所以显然会有 int[] f = new int[n + 1].

3) decode ways [91]
定义f[i] 是什么呢? 显然是 f[i] = number of ways to decode string up to ith position..

4) 再举个例子好了,
maximum subarray [53]
你如何给sum[i] 定义呢? 你当然可以说 s[i] = a[0] + ... + a[i], 或者 s[i] = a[0] + ... + a[i - 1].
如果你是第一种方式, 显然 int[] s = new int[n], 如果是第二种方式, 显然 int[] s = new int[n + 1]了.

定义不同解题代码也就不同.. 这都是根你怎么定义dp有关.

http://www.1point3acres.com/bbs/thread-314258-1-1.html

评分

参与人数 1大米 +5 收起 理由
pxu + 5 很有用的信息!非常感谢!

查看全部评分

回复

使用道具 举报

我的人缘0
sarahzjn 发表于 2018-7-12 09:20:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (882)
 
 
13% (141)  踩
你想想一个问题,啥时候空(代表dp[0])也是一个base case的时候一般就需要length + 1。多用于字符串的处理都dp。

评分

参与人数 1大米 +3 收起 理由
pxu + 3 很有用的信息!

查看全部评分

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
2006reload 发表于 2018-7-12 16:11:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
base case 可以是空的话就是n+1

评分

参与人数 1大米 +3 收起 理由
pxu + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-26 01:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表