动态规划篇
动态规划(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。
那么状态转移方程就可以写为：
where
#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,记录下到第个元素的时候, 第
个元素以及它之前的序列能组成的算数序列的长度
此外,这只是当的时候, 就有(0,1,2),(0,1,2,3)和(1,2,3), 可以确定(0,1,2,3)是算数序列的时候,(1,2,3)必定也是算数序列, 所以我们可以额外增加一个变量res,记录
到第
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
我们可以记录下切割到第个字符的时候, 能否匹配到数组中的单词.
- 子问题: 到第
- 状态转移: 前
同样,我们需要一个长度为字符串长度的dp数组, 记录下前
转移方程为:
此处因为substr(j,i)预设的是 截取第到第
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数组记录下到第个单词时(也就相当于第
个小问题)所能组成的最长单词链。我们用
记录从1到n个单词的位置，用
记录从0到第
单词的位置，这样以便判断第
个单词和第
个单词是否满足条件
这样我们可以得到一个转移方程：
按照这样的方程，我们可以得到：
当
i=2, j=0: ba--b
i=2, j=1: ba--a
到这里为止就已经出现了多种组合方式了，所以可以用最大的一种计算方式：
因为至少一个单词是自己的单词链，所以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数组记录到第个位置的时候，最长的等差序列长度。由于组成等差序列，数组长度至少需要大于等于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记录下到第个数字，等差
的数量：
DP = {1:{d:count},2:{d:count}...}，那么可以得到状态转移方程：
使用max是因为到第
#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数组，记录下到第个位置的时候，最长的增长链，那么状态转移方程如下:
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)的位置的走法就有
种走法
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个元素的时候，每份平均值的和的最大值。
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];
}
};
网友评论