算法题2:动态规划

题目如下：

子数组的问题一般会想到滑动窗口或者快慢指针，但是输入的数组不是有序的，无法判断左右指针什么条件进行移动，当求最大或者最小、最优类似的问题时，适合用动态规划，动态回归需要找出状态转移方程。

1.什么是动态规划

基本步骤

1. 定义状态
   明确问题的状态表示（例如 dp[i] 或 dp[i][j] 的含义）。
2. 状态转移方程
   描述如何从子问题的解推导出当前问题的解（递推关系）。
3. 初始化边界条件
   设置初始状态的值（如 dp[0] = 0）。
4. 计算顺序
   确定填表顺序（自底向上或自顶向下）。
5. 返回结果
   从状态表中提取最终解。

2.实现方式：

2.1 自顶向下（递归）

f(n) = f(n-1) + f(n-2)

f(n-1)与f(n-2)的计算过程和上面的公式一样

设置初始状态：f(0) = 0;f(1) = 1;

public class Solution {//使用哈希map，充当备忘录的作用Map<Integer, Integer> tempMap = new HashMap();public int numWays(int n) {// 先处理初始值，递归到初始值后就直接返回if (n == 0) {return 1;}if (n <= 2) {return n;}//先判断有没计算过，即看看备忘录有没有if (tempMap.containsKey(n)) {//备忘录有，即计算过，直接返回return tempMap.get(n);} else {tempMap.put(n, (numWays(n - 1) + numWays(n - 2)));return tempMap.get(n);}}
}

时间复杂度是O(n)，空间复杂度O(n)

2.2 自底向上（迭代）

public class Solution {public int numWays(int n) {if (n<= 1) {return 1;}if (n == 2) {return 2;}int a = 1;int b = 2;int temp = 0;//采用for循环的方式，只需要存储两个变量值即可for (int i = 3; i <= n; i++) {temp = a + b;a = b;b = temp;}return temp;}}

时间复杂度是O(n)，空间复杂度O(1)

常见场景：青蛙跳台阶；斐波那契数列

回头查看最开始的题目，

分析：对于每一个元素num，都会有一个判断，num与pre+num比大小，pre表示num之前(包含num)与num中的最大值，如果num>pre+num，则丢弃之前的结果，直接采用num作为局部最大的和；另外采用maxSum变量存储全局最大和。

public class sulution{public int maxSubArray(int[] nums){if(nums.length == 1){return nums[0];}//maxSum用于存储当前元素之前的最大数据和int maxSum = nums[0];//用pre代表包含当前元素之前的最大数组和int pre = 0;for(int num : nums){pre = Math.max(pre + num,num);maxSum = Math.max(maxSum,pre);}
}