CPT挂靠抽中H1B后被RFE

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 428|回复: 5
收起左侧

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

[复制链接] |试试Instant~
我的人缘3
pxu 发表于 2018-7-12 05:53:43 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  64% (330)
 
 
35% (183)  踩

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

您需要 登录 才可以下载或查看,没有帐号?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)   【踩】
全局: 顶  64% (330)
 
 
35% (183)  踩
格式好像有很大问题,还不让编辑:(. 不过问题很简单,什么时候dp的size用输入数组length, 什么时候应该用length+1.谢谢指教。
回复

使用道具 举报

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

评分

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

查看全部评分

回复

使用道具 举报

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

定义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

评分

参与人数 2大米 +10 收起 理由
sugar + 5 给你点个赞!
pxu + 5 很有用的信息!非常感谢!

查看全部评分

回复

使用道具 举报

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

评分

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

查看全部评分

回复

使用道具 举报

我的人缘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-11-18 14:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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