動(dòng)態(tài)規(guī)劃篇

動(dòng)態(tài)規(guī)劃(Dynamic Programming,DP),是一種優(yōu)化問(wèn)題的思路,其核心思想是:把一個(gè)問(wèn)題分解成多個(gè)不會(huì)被重復(fù)計(jì)算的子問(wèn)題, 是一個(gè)大而化小的過(guò)程. 一個(gè)問(wèn)題是否可以用動(dòng)態(tài)規(guī)劃解決,可以根據(jù):

問(wèn)題是否能被分解成多個(gè)子問(wèn)題
子問(wèn)題是否不涉及多次計(jì)算
能否從上一個(gè)子問(wèn)題推導(dǎo)出下一個(gè)子問(wèn)題的答案
所以, 動(dòng)態(tài)規(guī)劃具有三個(gè)要素:
問(wèn)題邊界---該問(wèn)題的任務(wù)
-最優(yōu)子結(jié)構(gòu)---問(wèn)題的階段
-狀態(tài)轉(zhuǎn)移方程---從上一個(gè)子問(wèn)題推導(dǎo)到下一個(gè)子問(wèn)題的公式

Longest Increasing Subsequence

input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

這道題讓求最大增長(zhǎng)字串長(zhǎng)度，分類為二分查找，可是想了半天并沒(méi)有想到如何使用而分查找，但是很符合動(dòng)態(tài)規(guī)劃的解題思路。

我們維護(hù)一個(gè)dp數(shù)組，其中dp[i]表示到第i個(gè)位置時(shí)候的的最大上升字串長(zhǎng)度，對(duì)于每一個(gè)nums[i]，從第一個(gè)數(shù)再搜索到i，如果發(fā)現(xiàn)某個(gè)數(shù)小于nums[i]，我們更新dp[i]，更新方法為dp[i] = max(dp[i], dp[j] + 1)，即比較當(dāng)前dp[i]的值和那個(gè)小于num[i]的數(shù)的dp值加1的大小，+1是因?yàn)槿绻麧M足這個(gè)條件，則長(zhǎng)度自然增長(zhǎng)1個(gè)。需要注意的是，第二層循環(huán)從0~i。
那么狀態(tài)轉(zhuǎn)移方程就可以寫為：
$dp_i = max(dp_i,dp_j+1)$ where $nums_i>nums_j, i\in{0,1,2...size}, j\in{0,1,2...i}$

#include <iostream>

#include <vector>

using namespace std;


class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};


int main(int argc, char const *argv[])
{
    Solution solu;
    vector<int> arr ={10,9,2,5,3,4};//{-2,-1};//{10,9,2,5,3,7,101,18};
    cout<<solu.lengthOfLIS(arr)<<endl;
    return 0;
}

Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

題目是算術(shù)切片, 給定一個(gè)序列, 如果一個(gè)至少長(zhǎng)度大于等于3的序列,其兩兩之差等于一個(gè)固定的數(shù),那么這個(gè)序列可以被稱之為算數(shù)序列. 我們被要求返回這樣的算數(shù)序列一共有幾個(gè)

比如看[1,2,3,4,5]這個(gè)序列, 因?yàn)殚L(zhǎng)度至少大于三,我們可以分解出如下的算數(shù)序列:
[1,2,3],[1,2,3,4],[1,2,3,4,5]
[2,3,4],[2,3,4,5]
[3,4,5]
總共6個(gè)算數(shù)序列, 再比如[1,3,5,8,9,10]:
[1,3,5],[8,9,10].
那么這道題目看能否分解為子問(wèn)題:

一個(gè)大的序列必定有小的序列組成(子問(wèn)題),比如[1,2,3,4]中的[1,2,3]就是一個(gè)小問(wèn)題
它的下一個(gè)序列是[1,2,3,4], 也是算數(shù)序列,那么這階段, 算數(shù)序列的個(gè)數(shù)就是前面的序列個(gè)數(shù)+本次的序列個(gè)數(shù)
綜上:我們可以得到狀態(tài)轉(zhuǎn)移方程,在此之前我們需要設(shè)定一個(gè)數(shù)組dp,記錄下到第 $i$ 個(gè)元素的時(shí)候, 第 $i-1$ 個(gè)元素以及它之前的序列能組成的算數(shù)序列的長(zhǎng)度
$dp[i] = dp[i-1]+1$
此外,這只是當(dāng) $i$ 等于一個(gè)固定起始位置時(shí)候的序列量, 要求總的序列量, 那么,比如[1,2,3,4]這個(gè)序列,當(dāng) $i=3$ 的時(shí)候, 就有(0,1,2),(0,1,2,3)和(1,2,3), 可以確定(0,1,2,3)是算數(shù)序列的時(shí)候,(1,2,3)必定也是算數(shù)序列, 所以我們可以額外增加一個(gè)變量res,記錄
到第 $i$ 個(gè)元素的時(shí)候,所有可能的組合產(chǎn)生的算數(shù)序列個(gè)數(shù)
$res+=dp[i]$

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int len =  A.size();
        int res = 0;
        vector<int> dp(len,0);
        if(len<3)
            return 0;
        
        for(int i=2;i<len;i++){
            if((A[i]-A[i-1]) == (A[i-1]-A[i-2]))
                dp[i] = dp[i-1]+1;
            res += dp[i];
        }

        return res;

    }
};

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

字符串分裂. 題目要求給定一個(gè)字符串和一個(gè)單詞數(shù)組, 試問(wèn)能否將該字符串切割, 并且切割出的字符串至少需要匹配到數(shù)據(jù)中的某個(gè)單詞, 匹配到單詞的次數(shù)>=1. 這個(gè)字符串只能按順序切割, 不能重復(fù)切.
一開(kāi)始,我們并不知道切割那里是最好的, 所有可以把這個(gè)字符串分解成多個(gè)小問(wèn)題--也就是多個(gè)小的字符串,比如:

l le lee,leet,leetc...leetcode

我們可以記錄下切割到第 $i$ 個(gè)字符的時(shí)候, 能否匹配到數(shù)組中的單詞.

子問(wèn)題: 到第 $i$ 個(gè)字符串為止, 是否能切割成功
狀態(tài)轉(zhuǎn)移: 前 $i$ 個(gè)字符能否被切割成功
同樣,我們需要一個(gè)長(zhǎng)度為字符串長(zhǎng)度的dp數(shù)組, 記錄下前 $i$ 個(gè)字符能否被切割成功
轉(zhuǎn)移方程為:
$dp[i]=substr(j,i) in array \\ 0<j<i\\ 1<=i<=arraylength \\ dp[j] = True$
此處因?yàn)閟ubstr(j,i)預(yù)設(shè)的是截取第 $j$ 到第 $i-1$ 的字串, 所以, $i$ 的位置要+1

string substr(string s,int start,int end){
    string sub_str = "";
    for(int i=start;i<end;i++){
        sub_str += s[i];
    }

    return sub_str;
}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.length();
        vector<bool> is_cuted(len+1,false);
        is_cuted[0] = true;

        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                string sub_str = substr(s,j,i);
                if(is_cuted[j] && (std::find(wordDict.begin(),wordDict.end(),sub_str)!=wordDict.end())){
                    is_cuted[i] = true;
                    break;
                }
            }
        }

        return is_cuted[len];
    }
};

Longest String Chain

Given a list of words, each word consists of English lowercase letters.
Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

題目給定一個(gè)單詞序列，每個(gè)單詞都是由小寫字母組成的，求最長(zhǎng)的單詞鏈，如果前一個(gè)單詞在其任意位置添加一個(gè)字母能組成后一個(gè)單詞的話，這樣這兩個(gè)單詞就構(gòu)成一個(gè)詞鏈。
例子如:["a","b","ba","bca","bda","bdca"],其最長(zhǎng)的單詞鏈為：["a","ba","bda","bdca"]

思路：看能不能分解成小問(wèn)題，其次小問(wèn)題是否能進(jìn)行推導(dǎo)得到下一個(gè)問(wèn)題的答案
我們可以把["a","b","ba","bca","bda","bdca"]這個(gè)大的序列拆分為多個(gè)小問(wèn)題：
['a', 'b']，["a","b","ba"]....這樣，求其最長(zhǎng)單詞鏈。其次，我們可以用一個(gè)DP數(shù)組記錄下到第 $i$ 個(gè)單詞時(shí)(也就相當(dāng)于第 $i$ 個(gè)小問(wèn)題)所能組成的最長(zhǎng)單詞鏈。我們用 $i$ 記錄從1到n個(gè)單詞的位置，用 $j$ 記錄從0到第 $i$ 單詞的位置，這樣以便判斷第 $i$ 個(gè)單詞和第 $j$ 個(gè)單詞是否滿足條件
這樣我們可以得到一個(gè)轉(zhuǎn)移方程：
$如果滿足條件\\ dp[i]=dp[i-1]+1\\ 一級(jí)循環(huán) break$
按照這樣的方程，我們可以得到：
當(dāng)

i=2, j=0: ba--b
i=2, j=1: ba--a

到這里為止就已經(jīng)出現(xiàn)了多種組合方式了，所以可以用最大的一種計(jì)算方式：
$如果滿足條件\\ dp[i]=max(dp[i],dp[j]+1)\\$
因?yàn)橹辽僖粋€(gè)單詞是自己的單詞鏈，所以DP數(shù)組初始化為1，在此之前需要對(duì)單詞序列進(jìn)行排序，按單詞長(zhǎng)度遞增。

class Solution {
public:

    int longestStrChain(vector<string>& words) {
        int len = words.size();
        vector<int> dp(len,1);

        auto cmp = [](string & a, string& b) {
            return a.size() < b.size();
        };
        sort(words.begin(), words.end(), cmp);

        int pre_max = 0;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if (isPre(words[j],words[i])){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            pre_max = max(pre_max,dp[i]);
            }
        }

        return pre_max;
    }
};

Longest Arithmetic Sequence

Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].

題目是最長(zhǎng)等差序列，給定一個(gè)數(shù)組，求兩數(shù)之差相同的最長(zhǎng)序列。
以 [20,1,15,3,10,5,8]為例，最長(zhǎng)等差序列為：[20，15，10，5]，公差為-5。
我們可以將這個(gè)大的數(shù)組切分為多個(gè)小長(zhǎng)度的數(shù)組組成，即分解為多個(gè)小問(wèn)題，用一個(gè)DP數(shù)組記錄到第 $i$ 個(gè)位置的時(shí)候，最長(zhǎng)的等差序列長(zhǎng)度。由于組成等差序列，數(shù)組長(zhǎng)度至少需要大于等于2：

i=1
j=0 d=1-10 = -9

i=2
j=0 d=15-20=-5
j=1 d=15-1 = 14

i=3
j=0 d=17
j=1 d=2
j=2 d=12

i=4
j=0 d=10
j=1 d=9
j=2 d= -5
j=3 d= 7
.....

經(jīng)過(guò)推導(dǎo)，我們可以用一個(gè)字典DP記錄下到第 $i$ 個(gè)數(shù)字，等差 $d$ 的數(shù)量：
DP = {1:{d:count},2:{d:count}...}，那么可以得到狀態(tài)轉(zhuǎn)移方程：

$dp[i][d] = dp[j][d]+1;\quad if \quad dp[j][d] \quad exists\\ dp[i][d] = 2; \quad if \quad dp[j][d] \quad not exists\\ ans = max(ans, dp[i][d]), ans init =0$
使用max是因?yàn)榈降?img class="math-inline" src="https://math.jianshu.com/math?formula=i" alt="i" mathimg="1">個(gè)的時(shí)候，也許存在很多的等差序列，我們?nèi)∑渥畲蟮哪莻€(gè)；不存在該等差的時(shí)候，賦值為2是因?yàn)槊恳粋€(gè)等差必有2個(gè)以上的數(shù)字所構(gòu)成

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int len = A.size();
        int res = 0;

        if(A.size()<2)
            return res;
        //vector<map<int,int>> dp(len);
        unordered_map<int, unordered_map<int, int>>dp;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                int gap = A[i]-A[j];

                if(!dp[j][gap]){
                    dp[i][gap] = 2;
                }
                else{
                    dp[i][gap] = dp[j][gap]+1;
                }
                
                res = max(res,dp[i][gap]);
            }
        }

        return res;
    }
};

int main(int argc, char const *argv[])
{
    Solution solu;
    std::vector<int> v3={20,1,15,3,10,5,8};
    std::vector<int> v1={3,6,9,12};
    std::vector<int> v2={9,4,7,2,10};
    std::vector<int> v4={24,13,1,100,0,94,3,0,3};

    cout<<solu.longestArithSeqLength(v3)<<endl;
    cout<<solu.longestArithSeqLength(v1)<<endl;
    cout<<solu.longestArithSeqLength(v2)<<endl;
    cout<<solu.longestArithSeqLength(v4)<<endl;

    return 0;
}

Maximum Length of Pair Chain

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

求最長(zhǎng)增長(zhǎng)鏈，給定一個(gè)序列，序列里面是數(shù)字對(duì)，增長(zhǎng)鏈定義為：
(a,b) (c,d), b<c即為一個(gè)增長(zhǎng)鏈，注意 a<b, c<d，每個(gè)數(shù)字對(duì)都遵循這個(gè)規(guī)律。

同樣可以分解為小問(wèn)題，同樣可以使用DP解題。我們用一個(gè)dp數(shù)組，記錄下到第 $i$ 個(gè)位置的時(shí)候，最長(zhǎng)的增長(zhǎng)鏈，那么狀態(tài)轉(zhuǎn)移方程如下:
$dp[i] = max(dp[i].dp[j]+1), if-follow-condition\\ //對(duì)于第i個(gè)位置時(shí)候，最長(zhǎng)的長(zhǎng)度\\ res = max(res,dp[i])\\ //計(jì)算增加一個(gè)位置，當(dāng)前最長(zhǎng)的增長(zhǎng)鏈$

bool cmp(vector<int> &a, vector<int> &b) {
            return a[1] < b[1];
        }


class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),cmp);

        int len = pairs.size();
        int res = 0;
        
        if(len<2)
            return res+1;

        vector<int> dp(len,1);
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(pairs[i][0]>pairs[j][1])
                    dp[i] = max(dp[i],dp[j]+1);
            }
            res = max(res,dp[i]);
        }
        return res;
    }
};

int main(int argc, char const *argv[])
{
    Solution solu;
    vector<vector<int>> arr = {{3,4},{1,2},{2,3}};
    vector<vector<int>> arr2 = {{9,10},{9,10},{4,5},{-9,-3},{-9,1},{0,3},{6,10},{-5,-4},{-7,-6}};
    cout<<solu.findLongestChain(arr)<<endl;
    cout<<solu.findLongestChain(arr2)<<endl;
    return 0;
}

Unique Path

一開(kāi)始想的太復(fù)雜，想要使用回溯簡(jiǎn)簡(jiǎn)單的解決這個(gè)問(wèn)題，最終發(fā)現(xiàn)回溯會(huì)導(dǎo)致TLE(時(shí)間超限)，下面看DP的思路。
對(duì)于到達(dá)最終位置，也就是矩陣的第(n,m)個(gè)位置，這里使用rows,cols來(lái)代表n,m，也就是矩陣的行和列。
令初始位置為(1,1)，機(jī)器人一共只有向下或者向右兩中走法。那么分解為子問(wèn)題，當(dāng)機(jī)器人要走到(2,2)這個(gè)位置的時(shí)候，自然只有2中走法：右->下; 下->右
我們用一個(gè)二維數(shù)組記錄下到第[i][j]個(gè)格子的時(shí)候，一共有多少種走法
要走到第n,m的時(shí)候：到第(i,j)的位置的走法就有
$dp[i][j] = dp[i-1][j]+dp[i][j-1]\\ 0<i<m\\ 0<j<n$
種走法

Largest Sum of Averages

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
Note that our partition must use every number in A, and that scores are not necessarily integers.
Example:
Input:
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation:
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

將一個(gè)數(shù)組分成不相交的K份，求每份平均值的和最大是多少。
這題很久都沒(méi)有思路，看到一個(gè)很有意思的解法
我們可以通過(guò)推導(dǎo)，將數(shù)組分割為多個(gè)小數(shù)組，以及k從1到k：

轉(zhuǎn)載自圖上網(wǎng)站

設(shè)計(jì)一個(gè)DP數(shù)組dp[k][i],存儲(chǔ)分為k組時(shí)，到第i個(gè)元素的時(shí)候，每份平均值的和的最大值。
$dp[k][i] = max(dp[k-1][j]+avg(a[j],a[j-1]))\\ k-1<=j<i\\ k<=i<len$

class Solution {
public:
  double largestSumOfAverages(vector<int>& A, int K) {
    int len = A.size();
    vector<vector<double>> dp(K, vector<double>(len, 0.0));
    vector<double> sums(len, 0.0);
    sums[0] = A[0];
    dp[0][0] = A[0];

    for (int i = 1; i <len; i++) {
      sums[i] = sums[i - 1] + A[i];
      dp[0][i] = (sums[i])/(i+1);
    }
    
    for (int k = 1; k < K; ++k)
      for (int i = k; i <len; ++i)
        for (int j = k - 1; j < i; ++j)
          dp[k][i] = max(dp[k][i], dp[k - 1][j] + (sums[i] - sums[j]) / (i - j));
    
    return dp[K-1][len-1];
  }
};

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

動(dòng)態(tài)規(guī)劃筆記

動(dòng)態(tài)規(guī)劃筆記

動(dòng)態(tài)規(guī)劃篇

Longest Increasing Subsequence

Arithmetic Slices

Word Break

Longest String Chain

Longest Arithmetic Sequence

Maximum Length of Pair Chain

Unique Path

Largest Sum of Averages

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

動(dòng)態(tài)規(guī)劃筆記

動(dòng)態(tài)規(guī)劃篇

Longest Increasing Subsequence

Arithmetic Slices

Word Break

Longest String Chain

Longest Arithmetic Sequence

Maximum Length of Pair Chain

Unique Path

Largest Sum of Averages

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av