动态规划学习总结
最近在学习算法，希望写一篇博客来记录自己学习过程和总结一下自己学到的东西，方便以后的归纳整理。我觉得写博客是一种很好的整理知识点的方法，在写的过程你可以认认真真的去归纳知识点，发现自己理解的不到位的地方，从而去提高自己。虽然需要花点时间，但是很有帮助。
下面我将从三个方面来介绍动态规划的内容。
1.动态规划介绍
2.动态规划的解题思路
3.动态规划例题分析
[TOC]
动态规划介绍
1.什么是动态规划
动态规划就是一种用来解决最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解的子问题的解都记录下来。这样当下次碰到同样的子问题的时候 ，直接使用之前记录的结果。而不是重复计算。
按我的理解来说，动态规划就是 自底向上求解，而一般的递归是自顶向下求解。当我们使用自底向上求解的时候，我们解决问题的时间复杂度就可以转化为O(n),从而大大优化我们的算法。但是问题来了，我们如何自底向下求解呢，不要着急，我们先来了解动态规划的基本性质。
2.动态规划三个重要概念
1.边界
边界问题是动态规划很重要的一个问题，因为我们在进行N次循环迭代的时候，要先找出初始问题的最优解，这就是我们说到底边界问题。及求出F(1),F(2)等初始值的最优解，一般这些边界的解我们很容易就可以得到。当我们分析出边界的最优解时，就可以通过循环迭代来求出整个问题的最优解。
2.最优子结构
最优子结构就是我们分解的每个子问题的解。由于动态规划是自底向上求解，所以我们在迭代的开始，只需要找到初始的计算边界问题，求出F(1),F(2)最小子问题的最优解，然后试着去寻找规律。
3.状态转移方程
状态转移方程是动态规划的核心，决定了问题的每一阶段和下一阶段的关系。我们在循环迭代的时候，其实每次迭代的核心逻辑就是使用状态转移方程寻找下一问题的最优解。
4.动态规划的适用场景
当我们遇到求什么最大值，最小值，最短路径等等类似问题的时候，我就就可以考虑是不是可以用动态规划的算法来解决问题。
说了这么多是不是有种一脸懵逼的感觉，我是谁？我在哪？我要干什么？喝口咖啡，下面咋们来通过一道例题来分析动态规划的解题套路。
动态规划解题思路
在学习了几道动态规划的问题后，我觉得动态规划问题还是有固定的解题思路的，下面我将自己的总结分享给大家。
首先先来一道例题。对应为Leetcode第53题。
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
拿到这道题，一看是求最大和，那就拿动态规划的方式来解决这道题吧。我们把动态规划的三大核心概念去分析这道题。
给定dp[]存储每个子问题的最优解,mums[]为给定的数组。
1.边界问题。
当给定的数组长度为0是，我们返回0.
2.最优子结构
本题是分析n数组的最大连续子数组的和，我们可以先求数组长度为1时的最优解，及F（1）的最优解。
F（1）：只能取-2 ，所以F（1）的最优解为-2
F（2）：1> -2+1 > -2, 所以F（2）的最优解为1
F（3）：.........
3.状态转移方程
F(n) = max（nums[n], nums[n] + F(n)）
为什么状态转移方程是这样的呢。我们来分析一下。
首先题目要求的是 连续子数组,我们必须保证我们所取到的每一个子问题的最优子结构都是连续子数组。所以我们从F（2）开始只有两种选择。
1.只选择nums[2]
2.选择 nums[2] + F（1）
这样才能保证取到的数组是连续子数组，我们只需要去取这两个结果 的最大值。
动态规划例题分析
最大子序和代码分析
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; //maxSum为最终结果
int curSum = 0; //curSum为动态和数
for (int i = 0; i < nums.length; i++) {
if (curSum < 0) {
//curSum<0，那么curSum没有利用价值了，直接至0；curSum>0，之后才有可能加出更大的和
curSum = 0;
}
curSum += nums[i];
if (curSum > maxSum) {
maxSum = curSum;
}
}
return maxSum;
}
理解动态规划我们可以先从简单问题入手，先把简答的问题搞懂然后一步一步去理解更难的动态规划问题。当然自己在平时还要多看代码，理解别人的解题思路。
网友评论