建设银陕西省分行网站,国内推广平台有哪些,专业的河南网站建设,直播平台创建公会看一遍就理解#xff1a;动态规划详解
- 什么样的问题可以考虑使用动态规划解决呢#xff1f;
如果一个问题#xff0c;可以把所有可能的答案穷举出来#xff0c;并且穷举出来后#xff0c;发现存在重叠子问题#xff0c;就可以考虑使用动态规划。 比如一些求最值的场景…看一遍就理解动态规划详解
- 什么样的问题可以考虑使用动态规划解决呢
如果一个问题可以把所有可能的答案穷举出来并且穷举出来后发现存在重叠子问题就可以考虑使用动态规划。 比如一些求最值的场景如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等都是动态规划的经典应用场景。
- 动态规划的解题思路
动态规划的核心思想就是拆分子问题记住过往减少重复计算。 并且动态规划一般都是自底向上的。
穷举分析确定边界找出规律确定最优子结构写出状态转移方程
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]1if (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;}
}
