动态规划（一）一一状态定义和状态转移方程

动态规划真让人看得头疼，这只是一种思想，并没有一定的解题规律，当问题出现的时候，对于不太熟悉动态规划的人来说，确实有点难以想到，一般都是采用暴力求法。这里贴一个知乎链接，我觉得动态规划讲的还挺好的，什么是动态规划？

嘿嘿，也不知道会不会有人还会跳回来看看，哈哈。反正是写给自己的，问题不大。既然理解了上面是动态规划，就来几个简单的题目来练练手（题目来源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的一些简单题型，但是做起来还是很费劲，算法这东西虚无缥缈又有迹可循。每做一种算法题型，无不在赞叹数学的厉害。现在也大致的了解了动态规划的一些解题思想，望后续继续深入理解。

废话不多了，请自己加油，希望看到这篇博客的人也一起共勉！