概念：
动态规划一般为自底向上的，不想递归是自顶向下，再自下回顶。

建立一个dp[]数组，来进行从0开始向后

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]);
if (max < dp[i]) {
max = dp[i];
}
}
return max;
}

509. 斐波那契数

int fib(int N) {
if (N < 1) return 0;
// 备忘录全初始化为 0
vector memo(N + 1, 0);
// 进行带备忘录的递归
return helper(memo, N);
}

int helper(vector& memo, int n) {
// base case
if (n == 1 || n == 2) return 1;
// 已经计算过
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}