動态規劃（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;
    }