动态规划问题

看一遍就理解：动态规划详解

- 什么样的问题可以考虑使用动态规划解决呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。 比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

- 动态规划的解题思路

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。 并且动态规划一般都是自底向上的。

穷举分析确定边界找出规律，确定最优子结构写出状态转移方程 dp[0][0][...] = 边界值 for(状态1 ：所有状态1的值){ for(状态2 ：所有状态2的值){ for(...){ //状态转移方程 dp[状态1][状态2][...] = 求最值 } } } 求解最大子段和 public static void main(String[] args) { int[] arr = new int[] {-1, 16, 1, -2, 3, -22, 1, -2, 4}; System.out.println(maxSubArray(arr)); } private static int maxSubArray(int[] arr) { if (arr.length == 0) { return 0; } int max = arr[0]; int sum = 0; for (int e : arr) { sum = (sum > 0 ? sum : 0) + e; max = Math.max(max, sum); } return Math.max(max, 0); } 青蛙跳问题 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。 // f(n) = f(n-1) + f(n-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 (int i = 3; i <= n; i++) { temp = (a + b) % 1000000007; a = b; b = temp; } return temp; } } 最长严格递增子序列的长度 class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; //初始化就是边界情况 dp[0] = 1; int maxans = 1; //自底向上遍历 for (int i = 1; i < nums.length; i++) { dp[i] = 1; //从下标0到i遍历 for (int j = 0; j < i; j++) { //找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1 if (nums[j] < nums[i]) { //因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i] dp[i] = Math.max(dp[i], dp[j] + 1); } } //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦 maxans = Math.max(maxans, dp[i]); } return maxans; } }