如何判断dp array size应该是len 还是 len +1

我在做动态规划的时候，不是很清楚什么时候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[i]){                    break;                }            [/i]
[i]}        [/i]
[i]}                [/i]
[i]return dp[len-1];        [/i]
[i]｝
但是，在其它题目里，比如说[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) {[/i]
[i]        // write your code here                [/i]
[i]if(s == null || s.isEmpty()) return 0;                [/i]
[i]int dp[] = new int[s.length()+1];        [/i]
[i]dp[0] = 1;        [/i]
[i]dp[1] = s.charAt(0)=='0'?0: 1;                [/i]
[i]for(int i = 2; i < s.length()+1; i++){            [/i]
[i]int first = Integer.valueOf(s.substring(i-1,i));            [/i]
[i]int second = Integer.valueOf(s.substring(i-2,i));                        [/i]
[i]if(first > 0 && first <=9){                dp[i] += dp[i-1];            }                        [/i][/i]
[i][i]if(second >= 10 && second <=26){                dp[i] += dp[i-2];            }        [/i][/i][/i]
[i][i][i]}                [/i][/i][/i]
[i][i][i]return dp[s.length()];                    [/i][/i][/i]
[i][i][i]}[/i][/i][/i]
[i][i][i]}




[/i][/i][/i]

格式好像有很大问题，还不让编辑:(. 不过问题很简单，什么时候dp的size用输入数组length, 什么时候应该用length+1.谢谢指教。

这取决于你dp[n] 是怎么定义的。。。。用length + 1只是因为需要用到dp[length]， 不这样初始化就越界了

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

你想想一个问题，啥时候空（代表dp[0]）也是一个base case的时候一般就需要length + 1。多用于字符串的处理都dp。

base case 可以是空的话就是n+1