老师好,我在用数组做动态规划算法题时,遇到个问题:
问题是爬楼梯的算法问题:
https://leetcode-cn.com/problems/climbing-stairs/
代码如下:
class Solution {
public int climbStairs(int n) {
if(n<=0) return 0;
if(n==1) return 1;
if(n==2) return 2;
int[] dp = new int[n];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}我的问题在第六行,在初始化数组时,因为for循环i到n就截止了,因此dp的最后条件是:
dp[n]=dp[n-1]+dp[n-2];
因此第六行创建初始化数组,我认为数组长度为n就够了,但是这里会出现 out of bounds的超出边界问题。
这里应该是初始化一个n+1 长度的数组,但是这里我不懂为什么会超出边界呢?谢谢