动态规划笔记

动态规划篇

动态规划(Dynamic Programming,DP),是一种优化问题的思路,其核心思想是:把一个问题分解成多个不会被重复计算的子问题, 是一个大而化小的过程. 一个问题是否可以用动态规划解决,可以根据:

  • 问题是否能被分解成多个子问题
  • 子问题是否不涉及多次计算
  • 能否从上一个子问题推导出下一个子问题的答案
    所以, 动态规划具有三个要素:
  • 问题边界---该问题的任务
    -最优子结构---问题的阶段
    -状态转移方程---从上一个子问题推导到下一个子问题的公式

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.

这道题让求最大增长字串长度，分类为二分查找，可是想了半天并没有想到如何使用而分查找，但是很符合动态规划的解题思路。

我们维护一个dp数组，其中dp[i]表示到第i个位置时候的的最大上升字串长度，对于每一个nums[i]，从第一个数再搜索到i，如果发现某个数小于nums[i]，我们更新dp[i]，更新方法为dp[i] = max(dp[i], dp[j] + 1)，即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小，+1是因为如果满足这个条件，则长度自然增长1个。需要注意的是，第二层循环从0~i。
那么状态转移方程就可以写为：
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.

题目是算术切片, 给定一个序列, 如果一个至少长度大于等于3的序列,其两两之差等于一个固定的数,那么这个序列可以被称之为算数序列. 我们被要求返回这样的算数序列一共有几个

比如看[1,2,3,4,5]这个序列, 因为长度至少大于三,我们可以分解出如下的算数序列:
[1,2,3],[1,2,3,4],[1,2,3,4,5]
[2,3,4],[2,3,4,5]
[3,4,5]
总共6个算数序列, 再比如[1,3,5,8,9,10]:
[1,3,5],[8,9,10].
那么这道题目看能否分解为子问题:

  • 一个大的序列必定有小的序列组成(子问题),比如[1,2,3,4]中的[1,2,3]就是一个小问题
  • 它的下一个序列是[1,2,3,4], 也是算数序列,那么这阶段, 算数序列的个数就是前面的序列个数+本次的序列个数
    综上:我们可以得到状态转移方程,在此之前我们需要设定一个数组dp,记录下到第i个元素的时候, 第i-1个元素以及它之前的序列能组成的算数序列的长度
    dp[i] = dp[i-1]+1
    此外,这只是当i等于一个固定起始位置时候的序列量, 要求总的序列量, 那么,比如[1,2,3,4]这个序列,当i=3的时候, 就有(0,1,2),(0,1,2,3)和(1,2,3), 可以确定(0,1,2,3)是算数序列的时候,(1,2,3)必定也是算数序列, 所以我们可以额外增加一个变量res,记录
    到第i个元素的时候,所有可能的组合产生的算数序列个数
    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

字符串分裂. 题目要求给定一个字符串和一个单词数组, 试问能否将该字符串切割, 并且切割出的字符串至少需要匹配到数据中的某个单词, 匹配到单词的次数>=1. 这个字符串只能按顺序切割, 不能重复切.
一开始,我们并不知道切割那里是最好的, 所有可以把这个字符串分解成多个小问题--也就是多个小的字符串,比如:

l le lee,leet,leetc...leetcode

我们可以记录下切割到第i个字符的时候, 能否匹配到数组中的单词.

  • 子问题: 到第i个字符串为止, 是否能切割成功
  • 状态转移: 前i个字符能否被切割成功
    同样,我们需要一个长度为字符串长度的dp数组, 记录下前i个字符能否被切割成功
    转移方程为:
    dp[i]=substr(j,i) in array \\ 0<j<i\\ 1<=i<=arraylength \\ dp[j] = True
    此处因为substr(j,i)预设的是 截取第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".

题目给定一个单词序列，每个单词都是由小写字母组成的，求最长的单词链，如果前一个单词在其任意位置添加一个字母能组成后一个单词的话，这样这两个单词就构成一个词链。
例子如:["a","b","ba","bca","bda","bdca"],其最长的单词链为：["a","ba","bda","bdca"]

思路：看能不能分解成小问题，其次小问题是否能进行推导得到下一个问题的答案
我们可以把["a","b","ba","bca","bda","bdca"]这个大的序列拆分为多个小问题：
['a', 'b']，["a","b","ba"]....这样，求其最长单词链。其次，我们可以用一个DP数组记录下到第i个单词时(也就相当于第i个小问题)所能组成的最长单词链。我们用i记录从1到n个单词的位置，用j记录从0到第i单词的位置，这样以便判断第i个单词和第j个单词是否满足条件
这样我们可以得到一个转移方程：
如果满足条件\\ dp[i]=dp[i-1]+1\\ 一级循环 break
按照这样的方程，我们可以得到：
当

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

到这里为止就已经出现了多种组合方式了，所以可以用最大的一种计算方式：
如果满足条件\\ dp[i]=max(dp[i],dp[j]+1)\\
因为至少一个单词是自己的单词链，所以DP数组初始化为1，在此之前需要对单词序列进行排序，按单词长度递增。

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].

题目是最长等差序列，给定一个数组，求两数之差相同的最长序列。
以 [20,1,15,3,10,5,8]为例，最长等差序列为：[20，15，10，5]，公差为-5。
我们可以将这个大的数组切分为多个小长度的数组组成，即分解为多个小问题，用一个DP数组记录到第i个位置的时候，最长的等差序列长度。由于组成等差序列，数组长度至少需要大于等于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
.....

经过推导，我们可以用一个字典DP记录下到第i个数字，等差d的数量：
DP = {1:{d:count},2:{d:count}...}，那么可以得到状态转移方程：

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是因为到第i个的时候，也许存在很多的等差序列，我们取其最大的那个；不存在该等差的时候，赋值为2是因为每一个等差必有2个以上的数字所构成

#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]

求最长增长链，给定一个序列，序列里面是数字对，增长链定义为：
(a,b) (c,d), b<c即为一个增长链，注意 a<b, c<d，每个数字对都遵循这个规律。

同样可以分解为小问题，同样可以使用DP解题。我们用一个dp数组，记录下到第i个位置的时候，最长的增长链，那么状态转移方程如下:
dp[i] = max(dp[i].dp[j]+1), if-follow-condition\\ //对于第i个位置时候，最长的长度\\ res = max(res,dp[i])\\ //计算增加一个位置，当前最长的增长链

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

一开始想的太复杂，想要使用回溯简简单的解决这个问题，最终发现回溯会导致TLE(时间超限)，下面看DP的思路。
对于到达最终位置，也就是矩阵的第(n,m)个位置，这里使用rows,cols来代表n,m，也就是矩阵的行和列。
令初始位置为(1,1)，机器人一共只有向下或者向右两中走法。那么分解为子问题，当机器人要走到(2,2)这个位置的时候，自然只有2中走法：右->下; 下->右
我们用一个二维数组记录下到第[i][j]个格子的时候，一共有多少种走法
要走到第n,m的时候：到第(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.

将一个数组分成不相交的K份，求每份平均值的和最大是多少。
这题很久都没有思路，看到一个很有意思的解法
我们可以通过推导，将数组分割为多个小数组，以及k从1到k：


转载自图上网站

设计一个DP数组dp[k][i],存储分为k组时，到第i个元素的时候，每份平均值的和的最大值。
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];
  }
};
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,254评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,875评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,682评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,896评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,015评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,152评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,208评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,962评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,388评论 1赞 304
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,700评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,867评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,551评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,186评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,901评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,142评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,689评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,757评论 2赞 351

推荐阅读更多精彩内容