我正在尝试学习动态规划的记忆化,我正在观看麻省理工学院在 youtube 上的视频,试图跟进它。我不知道如何将第 N 个值与数组进行比较。
int[] memo;
public int fib(int n) {
int f = 0;
if n is in memo then return memo[n] <----not sure how to code this line.
if (n<=2) {
f = 1;
} else {
f = fib(n-1) + fib(n-2);
}
memo[n] = f;
return f;
}
最佳答案
用 ArrayList
做:
ArrayList<Integer> memo = new ArrayList<Integer>();
public int fib(int n) {
if (memo.size() == 0)
memo.add(0); // element 0 is never accessed
return fib2(n);
}
private int fib2(int n) {
int f = 0;
if (n < memo.size())
return memo.get(n);
if (n<=2) {
f = 1;
} else {
f = fib2(n-2) + fib2(n-1);
}
memo.add(f); // elements inserted in order
return f;
}
用数组做:
int[] memo;
public int fib(int n) {
memo = new int[n+1]; // all initialized to 0
return fib2(n);
}
private int fib2(int n) {
int f = 0;
if (memo[n] != 0)
return memo[n];
if (n <= 2) {
f = 1;
} else {
f = fib2(n-2) + fib2(n-1);
}
memo[n] = f;
return f;
}
关于java - 动态规划的记忆化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14921294/