为什么很多DP问题的数组长度设置都是length+1

比如那道decode ways，可以：1）int[] dp = new int[s.length()+1]; 最后return dp[s.length()];
我觉得用2）int[] dp = new int[s.length()];  return dp[s.length()-1]; 也可以啊？ 在IDE上debug可以得出正确答案，但是在LC上提交后过不了，非要改成第一种情况才行，为什么呢？

这要看算法的具体实现，如果算法最后返回是dp[s.length()]，那多半说明作者的思路是将dp[i]看作是“intermediate result for the prefix of length i”；而如果算法最后返回dp[s.length()-1]，则暗示作者可能将dp[i]看做"intermediate result for the prefix up to the ith (0-based) character"，即““intermediate result for the prefix of length i+1”

在这两种不同思路下，数组的初始化方式，循环的起始和终止条件等都应稍有不同，并不是只修改dp的定义方式，而其他代码不需改变就可以从一种思路变换到另一种思路的。

谢谢，又做了几道DP题，慢慢摸出里面的规律了，但还不是很清楚，争取多练练，熟练掌握

我觉得之所以要+1是因为最后要return dp[num]. 对于dp的题目，我一直都不是很理解，最后都往往有Memorization+递归的方式解决。对于dp的理解就是问题可以划分成类似的子问题，可以考虑dp.呵呵，估计考到就挂了。

定义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有关.