动态规划本质依然是递归算法，只不过是满足特定条件的递归算法
什么是动态规划
将原问题拆解成若干子问题，同时保存子问题的答案，从而避免重复求解子问题
斐波那契数列
public int Fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}
考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。
public int fib(int n) {
if (n <= 1) {
return n;
}
int a1 = 0, a2 = 1, sum = 0;
for (int i = 2; i <= n; i++) {
sum = (a1 + a2) % 1000000007;
a1 = a2;
a2 = sum;
}
return sum;
}
LeetCode题解
第一个动态规划问题
leetcode 70. 爬楼梯
- leetcode 120
- leetcode 64
发现重叠子问题
LeetCode343整数拆分
- leetcode 279
- leetcode 91
- leetcode 62
- leetcode 63
状态的定义和状态转移
leetcode 198. 打家劫舍
198. House Robber
- leetcode 213
- leetcode 337
- leetcode 309