算法

动态规划

算法

Posted by Nova on 2020-02-01 
1
2
3
4
5
核心概念：最优子结构、状态转移方程、边界、重叠子问题
核心思想：拆分子问题；记住过往，减少重复计算
解题思路：穷举举例、确定边界、找规律、确定最优子结构、写出状态转移方程

> 记住求过的解来节省时间

举例: leetcode53-最大子数组和

输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6

思路

用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」.

这里为什么要限定 第i个数结尾? 因为f(i) 依赖f(i-1) 的连续.
状态转移方程：f(i) = Math.max(f(i-1) + nums[i], nums[i]). 含义:如果f(i-1)小于0,取nums[i]就够了.

怎么根据以上获取需求的解？
最大子数组的和 其实就是最大的f(i). 所以 maxV = Math.max(maxV, f(i)).

1
2
3
4
5
6
7
8
9
10
public static int maxSubArray(int[] nums) {
    // f(i) = Math.max(f(i-1)+nums[i], nums[i])
    int preSum = 0;
    int max = nums[0];
    for (int i=0;i<nums.length;i++) {
        preSum = Math.max(preSum+nums[i], nums[i]);
        max = Math.max(max, preSum);
    }
    return max;
}

动态规划

解题核心

  • 第一步：状态的定义
  • 第二步：状态转移方程的定义

最优子结构

能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。

无后效性

一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。
要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。
“未来与过去无关”，这就是无后效性。
（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）

常见问题

  • 青蛙跳阶问题
  • 凑零钱问题
  • 最长递增子序列
  • 最小编辑距离
  • 背包问题

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解
动态规划实际上是一类题目的总称，并不是指某个固定的算法

什么情况下考虑使用动态规划呢？

  • 如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

动态规划、分治法、贪心

  • 动态规划实际上是一类题目的总称，并不是指某个固定的算法。
  • 动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。
  • 动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

与分治法最大的差别是：适合于用动态规划法求解的问题，
经分解后得到的子问题往往不是互相独立的
（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）

分治法

子问题是相互独立的.

贪心

  1. 有效的括号字符串
  2. 跳跃游戏
  • 是寻找最优解问题的常用方法
  • 先找到【局部最优】, 并希望最后【堆叠出的结果】也是最好/最优的解
  • 好像一个贪婪的人，贪图眼前局部的利益最大化。看不到长远的东西

解题步骤

1
2
3
从某个初始解出发
采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模
将所有解综合起来

资料

什么是动态规划？动态规划的意义是什么？

java 动态规划策略原理及例题

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

FEATURED TAGS
算法
FRIENDS