动态规划真让人看得头疼，这只是一种思想，并没有一定的解题规律，当问题出现的时候，对于不太熟悉动态规划的人来说，确实有点难以想到，一般都是采用暴力求法。这里贴一个知乎链接，我觉得动态规划讲的还挺好的，什么是动态规划？
嘿嘿，也不知道会不会有人还会跳回来看看，哈哈。反正是写给自己的，问题不大。既然理解了上面是动态规划，就来几个简单的题目来练练手（题目来源leetcode）。
1 最大子序和
既然是采用的是动态规划，动态规划的是必要条件是无后效性。其思想是大事化小小事化了。也就是说将一个大问题转化成几个小问题，求出小问题，推出大问题的解。
首先，我们来进行状态的定义。我们假设v(i) 能表示下标为 i 时连续数组的最大和。状态的定义确实是个技术活。v(i) 是需要包含nums[ i ]的，这样才能保证连续性，也就是说，v[ i ]并不是代表的前i + 1 的最大子序列的和。而是包含nuns[i ]的最大子序列的和。
接下来就可以写出状态转移方程，v(i) = max(v(i - 1) + nums[i] , nums[ i ]),即下标为 i 时连续数组的最大和 肯定等于 nums[ i ] 和下标为 i - 1时连续数组的最大和 加上nums[ i ]的值中的最大的一个。这里为什么不是v(i) = max(v(i - 1) + nums[i] , v(i - 1))？这里需要解释一下，如果这么写的话，有可能v[ i] 和 v[i - 1] 是同一个子序且也不能实现是连续子序的要求。
边界就比较好取了，v(0 ) = nums[0]。我们把v[ i ] 中的最大值取出来，也就得出结果了。代码如下：
int maxSubArray(vector<int>& nums) { if(nums.empty()) return 0; vector<int> v(nums); int maxNum = nums[0]; for(int i = 1; i < nums.size(); i++) { v[i] = max(v[i - 1] + nums[i], nums[i]); if(maxNum < v[i]) maxNum = v[i]; } return maxNum; }我想大家都知道，对于动态规划的题目，只要能写出状态转移方程，那么题目也就差不多啊解出来了。难就难在这，状态的定义到底要怎么定义确实是个技术活。现在再来做一道题。
打家劫舍
这题和上一个题相仿，按着第一个题的分析我们来分析第二题。首先，还是进行状态的定义，还是写成v( i ) 吧，这样看的明白些，表示的是房屋为 i + 1 时能偷到的最高金额。
那么状态转移方程也就简单了，v(i) = max(v(i - 1), v(i - 2) + muns[i])， 这里我们不需要管v(i - 1) 和 v(i - 2 )是怎么来的，这就是无后效性。因为最后的求解是自底向上的，最要满足最开始的边界条件即可。
好了，边界条件也就一概写出来了，v[0] = nums[0], v[1] = max(nums[0], nums[1])。代码也就呼之欲出了：
int rob(vector<int>& nums) { if(nums.empty()) return 0; if(nums.size() == 1) return nums[0]; if(nums.size() == 2) return max(nums[1], nums[0]); int res; vector<int> v(nums.size()); v[0] = nums[0]; v[1] = max(nums[0], nums[1]); for(int i = 2; i < nums.size(); i++) { v[i] = max(v[i - 2] + nums[i], v[i - 1]); } return v[nums.size() - 1]; }接下来再看一题，不要睡觉，最后一题了，还都是简单题。
除数博弈
这里我们先撇开数学大神的一行代码求解。。。
老样子，状态定义，还是v(i) 吧（哈哈，简单嘛！），所以你想定义成啥嘛。这样吧，v( i )表示的是，当数字为 i 时，谁开始选择x，其是输（v( i ) = 0）还是赢（v( i ) = 1）。
状态定义了，接下来就是状态转移方程 ，我们假设 找到一个数为 i - m，满足0 < i - m < i 且 i % (i - m) == 0使得v(m) = 0,那么v(i)就是赢的，也就是v(i) = 1。代码如下：
bool divisorGame(int N) { vector<int> v(N+1,0); for(int k=1;k<=N;k++) { for(int m=1;m<k;m++) { if(k%(k-m)==0 && v[m]==0) { v[k]=1; break; } } } return v[N]; }如上，也就知道了每一个v(i) 的值了，只是因为是双重循环，所以时间复杂度达到了O(N²)。空间复杂度为O(N)。
以上都是leetcode的一些简单题型，但是做起来还是很费劲，算法这东西虚无缥缈又有迹可循。每做一种算法题型，无不在赞叹数学的厉害。现在也大致的了解了动态规划的一些解题思想，望后续继续深入理解。
废话不多了，请自己加油，希望看到这篇博客的人也一起共勉！