动态规划模糊点

有没有人跟我一样，总在动态规划最开始int[][] dp = new int[m+1][n+1]或者int[][] dp = new int[m][n]这里迷糊，看到有的题是m+1,n+1有的却是m,n。到底是什么情况下+1,什么情况不用+1?

感觉大概就是如果愿意从0开始计数就不用+1 但为了减少出错的机会 从1开始计数 这样就需要+1 这样数数的时候就不用想着-1了

可能有的问题从(0, 0)推到(m,n)比较方便, 有些从(1,1)推到(m,n)比较方便; 或者有时写dp[1,1]比dp[0,0]对应(1,1)更自然?

因为如果不+1，最大可访问位置是n-1，访问a[n]的时候数组会溢出

所以刷题的时候，空间能开大尽量开大，保险

这个还是看dp数组的意义，有些时候，比如prefix sum这个一般就需要+1，这样方便计算sub array的和。

有些时候需要一个空位置来推导第一个i（即i==0）时的值，那就n+1
此时dp_1是i为0时的值，所以i为n-1时存在dp_n里（dp长度为n+1）
有时候dp_i就是对应数据里的i，这时候dp_n-1就够了（长度为n）

一方面是为了方便，比如说很多时候递推式是dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j])，如果从0开始就会出错。
另一方面是在实际意义上就存在0的情况比如说knapsack 问题中的 dp[ i - val]. 如果 当前volumn = val，意味着放当前package之前，包是空的。

大概来说，就是定义了dp[n]，循环从 i=1开始，状态方程 dp[i] = dp[i - 1]......；定义了dp[n + 1]，循环直接i = 0开始，dp[i + 1] = dp[i]...，没有i-1了，就不会出现 dp[0-1]， 也就是dp[-1]这种数组index越界问题。

记得我在某个帖子里面回过，用到m+1的都是string match，因为多了空字符；其他记不得了

看下标为0时候的意义。如果下标为0表示空，使用m+1方便一点；如果表示一个值，m方便些。