动态规划（DP）算法学习记录

状态转移

解题步骤：

1.设计状态

2.写出状态转移方程

3.设定初始状态

4.执行状态转移

5返回最终的解

斐波那契数列 f[i] = f[i-1] + f[i-2] ：也可以叫 递推公式，或 状态转移方程。f[i] 就是状态的概念，从一个状态 f[i-1] 到另一个状态 f[i] 就叫状态转移。记得考虑初始状态 f[0] 和 f[1]。

1）leetcode题目

1. 斐波那契数列（第2332）

注意：每次都要判断是否大于100000007，防止overflow，且不使用递归，否则会导致超时。

int fib(int n) {
        vector<int> vInt;
        vInt.push_back(0);
        vInt.push_back(1);
        
        if(n == 0 || n==1)
        {
            return vInt[n];
        }else
        {
            for(int i = 2;i<=n;i++)
            {
                vInt.push_back(vInt[i-1] + vInt[i-2]);
                if(vInt[i] > 1000000007)
                {
                    vInt[i] = vInt[i] % 1000000007;//重点
                }
            }
            return vInt[n];
        }
        
    }
           

2. 爬楼梯

2.1 爬楼梯（70）

• 解析：假设数组 f[i] 表示从第0阶爬到第 i 阶的方案数，那么只能从 f[i-1] 或者 f[i-2] 爬上来该阶，所以 f[i] = f[i-1] + f[i-2]。

  倒着思考：先定义初始状态，然后补充后面的状态

int climbStairs(int n) {
        vector<int> vInt;
        vInt.push_back(0);//用掉0，让下标更好地匹配
        //定义初始状态
        vInt.push_back(1);
        vInt.push_back(2);
        //判断
        if( n == 1)
        {
            return vInt[1];
        }else if(n == 2)
        {
            return vInt[2];
        }else
        {
            for(int i = 3; i<=n ; i++)
                vInt.push_back(vInt[i-1] + vInt[i-2]);
        }
        return vInt[n];
    }
           

2.2 使用最小花费爬楼梯（746）

• 解析：

  假设数组 f[i] 表示爬到第 i 阶的最小花费，只能从 f[i-1] 或者 f[i-2] 爬上来该阶，即从 f[i-1] 或者 f[i-2] 转移过来，所以 f[i] = f[i-1] + cos[i-1] 或者 f[i-2] + cost[i-2] 。

  思考：

  先定义初始状态，然后补充后面的状态。最低下标为0的台阶，最高是爬上n上面的台阶到顶部，所以顶部的下标是sz+1。

int minCostClimbingStairs(vector<int>& cost) {
        //最低下标为0的台阶，最高是爬上n上面的台阶到顶部，所以顶部的下标是sz+1
        //设爬到第i个台阶的最小花费是minCost[i]
        decltype(cost.size()) sz = cost.size();
        vector<int> minCost(sz+1);//容器分配空间用圆括号
        minCost.push_back(0);
        minCost.push_back(0);
        for(decltype(cost.size()) i = 1; i<sz ; i++)
        {
            minCost[i+1] = ((minCost[i]+cost[i]) < (minCost[i-1]+cost[i-1]) ? 
                            (minCost[i]+cost[i]) : (minCost[i-1]+cost[i-1]));

        }
        return minCost[sz];//最然有sz+1个元素，但是最大下标是sz
    }
           

2.3 最大子数组和（53）

• 解析：

  如果枚举起点终点，那么一共有 n + n-1 + n-2 + …… + 1 = n(n-1)/2 个子数组，枚举三个for循环，时间复杂度O(n^3)，显然不可以直接枚举。

  以第 i 个整数结尾的子数组分为两种情况：

  1. 和第 i-1个整数结尾的子数组相连

  2. 和第 i-1个整数结尾的子数组不相连（即 单独以第 i 个整数作为子数组）

  状态转移方程：

  dp[ i ]表示以第 i 个整数结尾的子数组的最大值

  dp[ i ] = max{ dp[ i-1 ] + nums[ i ] , nums[ i ] }

  dp[0] = num[0];

int maxSubArray(vector<int>& nums) {
        vector<int> vInt(nums.size());
        int Max = nums[0];
        //以第i个数字结尾的子数组的最大和为vector[i]
        vInt[0] = nums[0];
        if(nums.size()>1)
        {
            for(decltype(nums.size()) i = 1; i<nums.size(); i++)
            {
                vInt[i] = (vInt[i-1]+nums[i]) > nums[i] ?
                            (vInt[i-1]+nums[i]) : nums[i];
            }
        }
        for(auto &curMax : vInt)
        {
            Max = curMax > Max ? curMax :Max;
        }
        return Max;
    }
           

3. 线性dp题，状态数和时间复杂度呈线性关系

3.1 打家劫舍（198）

• 解析：

  n 个整数，每个都可以选择取或者不取。

  1. 第 i 个取，则 i-1 不取，i-1 之前的随意，变成dp[ i-2 ]

  2. 第 i 个不取，那么 i 之前的可以取或者不取,变成dp[ i-1 ]

  状态转移方程：

  dp[ i ]表示前 i 个整数能够获得的最大值

  dp[ i ]取和不取，选取二者的最大值

  dp[ i ] = max{ dp[ i-2 ] + nums[ i ] , dp[ i-1 ] }

  dp[0] = num[0];

int rob(vector<int>& nums) {
        decltype(nums.size()) sz = nums.size();
        vector<int> vInt(sz);//此处会把sz个元素全部初始化为0
        vInt[0] = nums[0];//已经初始化了容量，不能用push_back，否则会添加到尾部
        if(sz>1)
        {
            vInt[1] = (nums[0]>nums[1] ? nums[0] : nums[1]);
            for(decltype(nums.size()) i = 2; i<nums.size(); i++)
            {
                vInt[i] = (vInt[i-2]+nums[i] > vInt[i-1] ? vInt[i-2]+nums[i] : vInt[i-1]);
            }
        }
        return vInt[sz-1];
    }
           

3.1 删除并获得点数

• 解析：

  简化题目如下，映射到一个数组中，此案成一个类似于hash的表格

  此时便和打家劫舍类似： 对于这个类似hash的数组，每次任选一个位置，选了以后相邻的位置不能再选。

  

  令 dp[ i ] 放入 数组 nums 中等于 i 的个数，类似于一种特殊的 hash 表。

  此时类似于打家劫舍，只不过 dp[ i ] 的下标 idp[ i ] 就是要的金额

  状态转移方程：

  dp[ i ]表示删除第 i 个整数能够获得的点数

  dp[ i ]取和不取，选取二者的最大值

  dp[ i ] = max{ dp[ i-2 ] + idp[ i ], dp[ i-1 ] }

  dp[0] = 0*dp[0];

int deleteAndEarn(vector<int>& nums) {
        vector<int> dp(10001);//nums最大是10000
        for(auto &a : nums)
        {
            dp[a] = dp[a]+1;
        }
        return rob(dp);
    }

    int rob(vector<int>& nums) //用微改后的打家劫舍的代码，只是此时nums的下标变成了值
    {
    nums[0] = 0;//已经初始化了容量，不能用push_back，否则会添加到尾部
    int max = 0;
    //直接对传进来的dp[]进行修改，此时nums[i]表示前i个整数能够获得的最大值
    if(nums.size()>1)
    {
        for(decltype(nums.size()) i = 2; i<nums.size(); i++)
        {
            nums[i] = (nums[i-2]+i*nums[i] > nums[i-1] ? nums[i-2]+i*nums[i] : nums[i-1]);
            max = max>nums[i] ? max:nums[i];//取vInt中最大值
        }
    }
    return max;
    }