Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
LeetCode / 动态规划
|LeetCode动态规划

动态规划dp

img

  • 动态规划和贪心算法的区别

    • 贪心算法：每一步最优解包含上一步最优解，上一步最优解不保留
      • 从根节点到叶子节点
    • 动态规划：穷举法，全局一定包含某个局部最优解，因此保留局部最优解。由局部最优解拼接而成的最优解。
      • 从叶子节点到根节点

背包问题

  • DP:统计次数、回溯:返回具体案例

img

01背包

Sum = target 的01背包问题(使用一次)
img

  • 题目：有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

根据上一行的情况进行求解 

1
2
3
4
5
//dp方程
if (j < Size[i])
	dp[i][j] = dp[i - 1][j];
else
	dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Size[i]] + Value[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	//01背包问题——固定size = 8,装最多的东西value
	vector<int>Size{ 2,3,4,5 };
	vector<int>Value{ 3,4,5,6 };

	int len = Size.size();
	int target = 8;
	vector<vector<int>>dp(len + 1, vector<int>(target + 1, 0));
	dp[0][0] = 0;
	for (int i = 1; i < len + 1; i++) {
		for (int j = 1; j < target + 1; j++) {
			if (j < Size[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j],   dp[i - 1][j - Size[i]] + Value[i]);
		}

	}
	cout << dp[len][target];
	return 0;
}

//优化
vector<int>dp(target + 1, 0);
for (int i = 0; i < len; i++) {
	int need = Size[i];
	int value = Value[i];
	for (int j = target; j >= need; j--) {
		dp[j] = max(dp[j], dp[j - need] + value);
	}
}

416.分割等和子集（01背包）

  • 一维：dp[len][target]

  • 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  • 输入: [1, 5, 11, 5]

  • 输出: true

  • 解释: 数组可以分割成 [1, 5, 5] 和 [11].

  • 输入: [1, 2, 3, 5]

  • 输出: false

  • 解释: 数组不能分割成两个元素和相等的子集.
    img

dp[target] = dp[Sum/2]

  • 解：target = Sum / 2，所以dp方程的定义就是在于dp[0]到dp[Sum/2]

    • 以一个数可以组成的sum，以两个数可以组成的sum
  • 动态方程：以一个或两个，依次往上加能组成的情况
    • dp[i][j] = dp[i-1][j]——继承上
    • 当j >= nums[i],dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool canPartition(vector<int>& nums) {
	//求取target
	int n = nums.size();
	if (n <= 1)return false;

	int sum = 0;
	for (auto it : nums) {
		sum += it;
	}
	if (sum % 2 == 1)return false;
	int target = sum / 2;

	vector<vector<bool>>dp(n + 1, vector<bool>(target + 1, 0));
	//dp方程:1.当nums[i]<j    dp[i][nums[i]] = true
	//       2.              dp[i][j]=dp[i-1][j]           上满足,下肯定满足
	//       3.              dp[i][j]=dp[i-1][j-nums[i]]   上满足,加上新num肯定满足

	//因为包含dp[i-1],所以需要多初始化一行,或者手动初始化第一行
	dp[0][0] = true;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= target; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= nums[i - 1])
				dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
		}
		if (dp[i][target])return true;
	}
	return dp[n][target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//优化版本
bool canPartition(vector<int>& nums) {
	int sum = 0;
	for (auto it : nums)
		sum += it;

	if (sum % 2 == 1) return false;
	int target = sum / 2;

	//转化 target = sum/2 的 01 背包问题
	vector<bool>dp(target + 1, false);
	dp[0] = true;
	for (int i = 0; i < nums.size(); i++) {
		int sizeNeed = nums[i];
		for (int j = target; j >= sizeNeed; j--)
			dp[j] = dp[j] || dp[j - sizeNeed];
	}
	return dp[target];
}

474.一和零(多维01背包)

  • 一维：dp[len][m]

  • 二维：dp[len][m][n]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int findMaxForm(vector<string>& strs, int m, int n) {
    	//每次都覆盖上一层,所以构造的是二维
    	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    	//二维费用背包问题 初始dp[0][0] = 0;
    	//dp[i][j]表示i个0j个1的情况下，最多可以拼出的个数
    	for (int i = 0; i < strs.size(); i++) {
    		int numOf0 = get0(strs[i]);
    		int numOf1 = get1(strs[i]);
    		for (int j = m; j >= numOf0; j--)
    			for (int k = n; k >= numOf1; k--)
    				//不选当前字符串 dp[i][j] , 选当前字符串 dp[j - numOf0][k - numOf1] + 1
    				//取二者最大值
    				dp[j][k] = max(dp[j][k], dp[j - numOf0][k - numOf1] + 1);
    	}
    	return dp[m][n];
    }

    int get0(string& s) {
    	int ret = 0;
    	for (int i = 0; i < s.size(); i++)
    		if (s[i] == '0') ret++;
    	return ret;
    }
    int get1(string& s) {
    	int ret = 0;
    	for (int i = 0; i < s.size(); i++)
    		if (s[i] == '1') ret++;
    	return ret;
    }

1049.最后一块石头的重量 II

  • 一维：dp[len][ sum / 2 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lastStoneWeightII(vector<int>& stones) {
	//转换求target = sum/2最接近的
	int sum = 0;
	for (auto it : stones)
		sum += it;
	int target = sum / 2;

	//尽可能装最多的石头
	vector<int>dp(target + 1);
	for (int i = 0; i < stones.size(); i++) {
		int need = stones[i];
		for (int j = target; j >= need; j--) {
			dp[j] = max(dp[j], dp[j - need] + need);
		}
	}
	return sum - 2 * dp[target];
}

—————————

完全背包（统计个数）

322.零钱兑换(完全背包)—硬币组成Min

  • 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

  • 输入: coins = [1, 2, 5], amount = 11

  • 输出: 3

  • 解释: 11 = 5 + 5 + 1

  • 输入: coins = [2], amount = 3

  • 输出: -1

img

  • 组成1块钱的最少硬币个数、组成2块钱的最少硬币个数

    • 所以组成N块钱的最少硬币个数 = min(f（N-coins[0]）,f（N-coins[1]）,f（N-coins[2]）)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// dfs可以做,但是超时
// int res = INT_MAX;
// int coinChange(vector<int>& coins, int amount) {
//     if(amount == 0)
//         return 0;

//     sort(coins.begin(),coins.end());
//     dfs(coins,0,0,amount);
//     return res==INT_MAX?-1:res;
// }
// void dfs(vector<int>& coins,int index,int cnt,int amount){
//     if(amount == 0){
//         res = min(cnt,res);
//         return;
//     }
//     if(amount < 0)
//         return;

//     for(int i = index;i<coins.size();i++){
//         if(amount - coins[i]<0)
//             break;
//         dfs(coins,i,cnt+1,amount-coins[i]);
//     }
// }
int coinChange(vector<int>& coins, int amount) {
	if (amount == 0)
		return 0;
	vector<int>dp(amount + 1, 99999);

	//初始化
	dp[0] = 0;
	for (int i = 0; i < coins.size(); i++) {  //i是钱总数
		for (int j = 1; j <= amount; j++) {
			if (j >= coins[i])
				dp[j] = min(dp[j], dp[j - coins[i]] + 1);
		}

	}
	return   dp[amount] == 99999 ? -1 : dp[amount];
}

518.零钱兑换II(完全背包)—硬币组成Sum

  • 类似leetcode39.组合中元素和为Sum（无重复元素、任意次数使用）

  • 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

  • 输入: amount = 5, coins = [1, 2, 5]

  • 输出: 4

  • 解释: 有四种方式可以凑成总金额:

  • 5 = 5

  • 5 = 2+2+1

  • 5 = 2+1+1+1

  • 5 = 1+1+1+1+1

img

  • dp方程：dp[ i ][ j ] = dp[ i -1][ j ] + dp[ i ][ j - coin[ i - 1 ] ]

    • 1.不用新的硬币—————— 2.用新的硬币，去除一个至少用一次
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      // int change(int amount, vector<int>& coins) {
      //     int N = coins.size();
      //     vector<vector<long> > dp(N + 1, vector<long>(amount + 1, 0));

      //     //dp[len][target]
      //     //len:代表使用种类
      //     //target:代表目标

      //     dp[0][0] = 1;          
      //     for (int i = 1; i <= N; i++) {
      //         dp[i][0] = 1;
      //         for (int j = 1; j <= amount; j++) {
      //             //不用新硬币
      //             dp[i][j] = dp[i - 1][j];
      //             //用新硬币——会逐步考虑
      //             if(j >=coins[i-1])
      //                 dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]];
      //         }
      //     }
      //     return dp[N][amount];
      // }
      //优化
      int change(int amount, vector<int>& coins) {
      	int N = coins.size();
      	vector<long>dp(amount + 1, 0);

      	//dp[len][target]
      	//len:代表使用种类
      	//target:代表目标

      	dp[0] = 1;
      	for (int i = 1; i <= N; i++) {
      		for (int j = 1; j <= amount; j++) {
      			//用新硬币——会逐步考虑
      			if (j >= coins[i - 1])
      				dp[j] = dp[j] + dp[j - coins[i - 1]];
      		}
      	}
      	return dp[amount];
      }

—————————

53.最大子序和

  • 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  • 输入: [-2,1,-3,4,-1,2,1,-5,4]

  • 输出: 6

  • 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

  • 简单DP，遇负反转。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    //常规DP
    int maxSubArray(vector<int>& nums) {

    	 int res = nums[0];
    	 int len = nums.size();
    	 vector<int>dp(len+1,0);
    	 for(int i = 1;i<len+1;i++){
    	     dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);
    	     res = max(res,dp[i]);
    	 }
    	 return res;
    }

    //贪心算法
    int maxSubArray(vector<int>& nums) 
    {
    	int res = nums[0];
    	int sum = 0;
    	for (auto it : nums) {
    		if (sum > 0)
    			sum += it;
    		else {
    			sum = it;
    		}
    		res = max(sum, res);
    	}
    	return res;
    }

300.最长上升子序列

  • 给定一个无序的整数数组，找到其中最长上升子序列的长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    // N^2：动态规划，暴力
    int lengthOfLIS(vector<int>& nums) {
    	if (nums.size() == 0)
    		return 0;

    	int res = 0;
    	vector<int>dp(nums.size(), 1);
    	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 lengthOfLIS(vector<int>& nums) {
    	if (nums.size() == 0)
    		return 0;

    	int len = nums.size();
    	vector<int>res;
    	vector<int>lenlen;
    	res.emplace_back(nums.front());
    	lenlen.emplace_back(1);
    	for (int i = 1; i < len; i++) {
    		if (nums[i] > res.back()) {
    			res.emplace_back(nums[i]);
    			lenlen.emplace_back(res.size());
    		}
    		else {//元素坐标
    			int pos = lower_bound(res.begin(), res.end(), nums[i]) - res.begin();
    			res[pos] = nums[i];
    			lenlen.emplace_back(pos + 1);
    		}
    	}
    	return res.size();
    }

1143.最长公共子串

  • 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

  • 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

  • 若这两个字符串没有公共子序列，则返回 0。

  • 输入：text1 = “abcde”, text2 = “ace”

  • 输出：3

  • 解释：最长公共子序列是 “ace”，它的长度为 3。

  • 输入：text1 = “abc”, text2 = “abc”

  • 输出：3

  • 解释：最长公共子序列是 “abc”，它的长度为 3。

img

  • dp方程

  • if（text1[ i-1 ]=text2[ j-1]）
    • dp[ i ][ j ] = dp[i-1 ][ j-1 ] +1;
  • else
    • dp[ i ][ j ] = max(dp[i-1 ][ j ],dp[i ][ j-1 ];)

如果要返回最长子串：需要进行反向回溯 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
string LCS(string s1, string s2) {
	int len1 = s1.size();
	int len2 = s2.size();
	vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1, 0));

	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			if (s1[i - 1] == s2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	cout << dp[len1][len2] << endl;

//如果要求最长子串具体的话，需要如下方式
	string res;
	int i = len1;
	int j = len2;
	while (1) {
		if (i == 0 || j == 0) 
			break;
		else {
			if (dp[i - 1][j] == dp[i][j]) {
				i--;
				continue;
			}
			else if (dp[i][j - 1] == dp[i][j]) {
				j--;
				continue;
			}
			else {
				res += s1[i-1];
				i--;
				j--;
			}
		}
	}
	reverse(res.begin(), res.end());
	
	cout << res;
	return res;
}

最长公共子串(连续)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string LCS(string str1, string str2) {
	// write code here
	int len1 = str1.size();
	int len2 = str2.size();
	int res = 0;
	int pos = 0;
	vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1, 0));
	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (dp[i][j] > res) {
					res = dp[i][j];
					pos = i - 1;
				}
			}
		}
	}
	if (res == 0)return "-1";
	return str1.substr(pos - res + 1, res);
}

72.编辑距离str1->str2

  • 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

  • 你可以对一个单词进行如下三种操作：

  • 1.插入一个字符

  • 2.删除一个字符

  • 3.替换一个字符

  • 输入：word1 = “horse”, word2 = “ros”

  • 输出：3

    • 解释：

  • horse -> rorse (将 ‘h’ 替换为 ‘r’)

  • rorse -> rose (删除 ‘r’)

  • rose -> ros (删除 ‘e’)

  • dp方程：

    • int temp1 = dp[i-1][j] + 1;
    • int temp2 = dp[i][j-1] + 1;
    • int temp3 = dp[i-1][j-1];
    • if(word1[i-1]!= word2[j-1])
      • temp3++;
    • dp[i][j] = min(temp1,min(temp2,temp3));

img

插入、删除、替换代价都是1，当当前的字符串相等的时候，替换代价为0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int minDistance(string word1, string word2) {
	//word1转换为word2
	int len1 = word1.size();
	int len2 = word2.size();

	if (len1*len2 == 0)return max(len1, len2);

	vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1));//都要+1  dp[0][0]

	for (int i = 0; i < len1 + 1; i++) {
		dp[i][0] = i;
	}
	for (int i = 0; i < len2 + 1; i++) {
		dp[0][i] = i;
	}
	for (int i = 1; i < len1 + 1; i++) {
		for (int j = 1; j < len2 + 1; j++) {
			int temp1 = dp[i - 1][j] + 1;
			int temp2 = dp[i][j - 1] + 1;
			int temp3 = dp[i - 1][j - 1];
			if (word1[i - 1] != word2[j - 1])
				temp3++;
			dp[i][j] = min(temp1, min(temp2, temp3));
		}
	}
	return dp[len1][len2];
}

118.杨辉三角的生成

  • 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

  • 输入: 5

  • 输出:
  • [
  • [1],
  • [1,1],
  • [1,2,1],
  • [1,3,3,1],
  • [1,4,6,4,1]
  • ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> generate(int numRows) {

	//初始化
	vector<vector<int>> res;
	for (int i = 1; i <= numRows; ++i)
		res.push_back(vector<int>(i, 1));

	for (int i = 2; i < numRows; ++i) {
		//赋值给第二个元素到倒数第二个元素
		for (int j = 1; j < i; ++j)
			res[i][j] = res[i - 1][j - 1] + res[i - 1][j];

	}
	return res;
}

120. 三角形最小路径和

  • 从下往上：减少判断、减少复杂度

img 

1
2
3
4
5
6
7
8
9
10
int minimumTotal(vector<vector<int>>& triangle) {

	int n = triangle.size();
	for (int i = n - 2; i >= 0; i--) {
		for (int j = 0; j <= i; j++) {
			triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
		}
	}
	return triangle[0][0];
}

22.括号生成的种类

  • 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  • 输入：n = 3

  • 输出：[

  • “((()))”,

  • “(()())”,

  • “(())()”,

  • “()(())”,

  • “()()()”

  • ]

  • 解：

  • （ 左 ） 右

  • 1组

    • （ ）

  • 2组

    • （ dp[0] ） dp[1]
    • （ dp[1] ） dp[0]

  • 3组

    • （ dp[0] ） dp[2]
    • （dp[1] ） dp[1]
    • （dp[2] ） dp[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<string> generateParenthesis(int n) {
	if (n == 0) return { "" };
	if (n == 1)return { "()" };

	vector<vector<string>>dp(n + 1);
	dp[0] = { "" };
	dp[1] = { "()" };

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			for (string p : dp[j])
			{     //左和右的不同组合，添加到vector中去，使用vector添加
				for (string q : dp[i - j - 1])
				{
					string str = "(" + p + ")" + q;
					dp[i].push_back(str);
				}
			}
		}
	}
	return dp[n];
}

300.最长上升序列(类似阿里面试题)

  • 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

  • 两种思路

    • dp方程O（n^2）
    • 元素替换O（n*logN）
      • 创建数组，每次进来一个元素都替换一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLIS(vector<int>& nums) {
	if (nums.size() == 0)
		return 0;

	int res = 0;
	vector<int>dp(nums.size(), 1);
	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;
}

阿里真题:字符串拼接

  • 给出一系列字符串，拼接成最长的字符串

  • 输入：

  • ab

  • abcd

  • cde

  • fgh

  • 输出：ab + cde + fgh

  • 解：这里的target就是dp[0]、dp[a]、dp[b]，一直到26个字母的最后一个dp[z]

  • 动态方程：以末尾字符排序，dp[index]表示以index结尾最长连续字符串

    • index不存在，dp[index] = dp[index-1]
    • index存在，dp[index] = arr[index] + dp[arr[first]-1],比较大小留下最大的
    • arr遍历完成，return，数组弹出。
      • 用到的方法：vector合并：
      • vecNew.insert(vecNew.end(),vec1.begin(),vec1.end());
      • vecNew.insert(vecNew.end(),vec2.begin(),vec2.end());

945. 使数组唯一的最小增量

  • 给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

  • 返回使 A 中的每个值都是唯一的最少操作次数。

  • 输入：[1,2,2]

  • 输出：1

  • 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minIncrementForUnique(vector<int>& A) {
	if (A.size() == 0)
		return 0;
	sort(A.begin(), A.end());
	int res = 0;

	for (int i = 1; i < A.size(); i++) {
		if (A[i] <= A[i - 1]) {
			int temp = A[i];
			A[i] = A[i - 1] + 1;
			res = res + A[i] - temp;
		}

	}
	return res;
}

983.最低票价

  • 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

  • 火车票有三种不同的销售方式：

  • 一张为期一天的通行证售价为 costs[0] 美元；

  • 一张为期七天的通行证售价为 costs[1] 美元；

  • 一张为期三十天的通行证售价为 costs[2] 美元。

  • 通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

  • 返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

  • 输入：days = [1,4,6,7,8,20], costs = [2,7,15]

  • 输出：11

  • 解释：

  • 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：

  • 在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生- 效。

  • 在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, …, 9 天生效。

  • 在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。

  • 你总共花了 $11，并完成了你计划的每一天旅行。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    int mincostTickets(vector<int>& days, vector<int>& costs) {
    	int len = days.back();
    	int a = 0;
    	int b = 0;
    	int c = 0;
    	//max({a,b,c})

    	vector<int>dp(len + 1, 0);
    	//记录需要出行日期
    	for (int i = 0; i < days.size(); i++) {
    		dp[days[i]] = -1;
    	}
    	for (int i = 1; i <= len; i++) {

    		if (dp[i] == 0)//当天不需要出行
    			dp[i] = dp[i - 1];
    		else {       //当天需要出行
    			a = dp[i - 1] + costs[0];
    			if (i - 7 >= 0)
    				b = dp[i - 7] + costs[1];
    			else
    				b = costs[1];

    			if (i - 30 >= 0)
    				c = dp[i - 30] + costs[2];
    			else
    				c = costs[2];
    		}
    		dp[i] = min({ a,b,c });
    	}
    	return dp[len];
    }

63.不同路径

  • 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

  • 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

  • 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

  • dp方程：

    • if (i == 0 && j == 0) dp[i][j] = 1;
    • else if (i == 0) dp[i][j] = dp[i][j - 1];
    • else if (j == 0) dp[i][j] = dp[i - 1][j];
    • else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	//dp[i][j] = dp[i-1][j] + dp[i][j-1]
	int lenX = obstacleGrid.size();
	int lenY = obstacleGrid[0].size();
	vector<vector<int>>dp(lenX, vector<int>(lenY, 0));

	for (int i = 0; i < lenX; i++) {
		for (int j = 0; j < lenY; j++) {
			if (obstacleGrid[i][j] == 1) {
				dp[i][j] = 0;
			}
			else {
				if (i == 0 && j == 0) dp[i][j] = 1;
				else if (i == 0) dp[i][j] = dp[i][j - 1];
				else if (j == 0) dp[i][j] = dp[i - 1][j];
				else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	return dp[lenX - 1][lenY - 1];
}

1277. 统计全为 1 的正方形子矩阵

  • 输入：matrix =

  • [
  • [0,1,1,1],
  • [1,1,1,1],
  • [0,1,1,1]
  • ]
  • 输出：15
  • 解释：
  • 边长为 1 的正方形有 10 个。
  • 边长为 2 的正方形有 4 个。
  • 边长为 3 的正方形有 1 个。
  • 正方形的总数 = 10 + 4 + 1 = 15.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int countSquares(vector<vector<int>>& matrix) {
    	int m = matrix.size(), n = matrix[0].size();
    	vector<vector<int>> f(m, vector<int>(n));
    	int res = 0;
    	for (int i = 0; i < m; ++i) {
    		for (int j = 0; j < n; ++j) {
    			if (i == 0 || j == 0)
    				f[i][j] = matrix[i][j];
    			else if (matrix[i][j] == 0)
    				f[i][j] = 0;
    			else
    				f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;

    			res += f[i][j];
    		}
    	}
    	return res;
    }

面试17.16按摩师 / 198. 打家劫舍

  • 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

  • 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  • 输入：[1,2,3,1]

  • 输出：4

  • 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。

  • 输入：[2,7,9,3,1]

  • 输出：12

  • 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

  • 解：就是不能连续偷窃

    • dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int rob(vector<int>& nums) {
	int len = nums.size();
	if (len == 0)
		return 0;
	else if (len == 1)
		return nums[0];

	vector<int>dp(len + 1, 0);
	dp[0] = 0;
	dp[1] = nums[0];

	for (int i = 2; i <= len; i++) {
		dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
	}
	return max(dp[len], dp[len - 1]);
}

用多个数组储存状态
用多个数组储存状态

————————

dp分状态的题目

字节真题：爬楼梯

  • 输入：一个人跳楼梯，可以跳一格，可以跳两格，但不能连续跳两格，问跳到nn层有多少种方式。（0\le n < 1000≤n<100）

  • 解：
    img

978. 最长湍流子数组

  • 数组的形式是升降升降升，这种形式

  • 输入：[9,4,2,10,7,8,8,1,9]

  • 输出：5

  • 解释：(A[1] > A[2] < A[3] > A[4] < A[5])

  • 题解：compare前后数据——遍历一遍数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// dp[i][0]表示以第i个元素结尾且是 下降 的最长的长度
// dp[i][1]表示以第i个元素结尾且是 上升 的最长的长度
int maxTurbulenceSize(vector<int>& A) {
	int n = A.size();
	if (n == 1)
		return 1;
	vector<vector<int>>dp(n, vector<int>{1, 1});
	int res = 0;
	for (int i = 1; i < n; i++) {
		if (A[i] > A[i - 1])
			dp[i][1] = dp[i - 1][0] + 1;
		if (A[i] < A[i - 1])
			dp[i][0] = dp[i - 1][1] + 1;
		res = max(res, max(dp[i][0], dp[i][1]));
	}
	return res;
}

121. 买卖股票的最佳时机(交易一次)

  • 贪心算法：求取价格最小的当天，然后进行两数相减

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int maxProfit(vector<int>& prices) 
    {
        int maxNum = 0;
        int maxDay = 0;

        for(int i= 0;i<prices.size();i++)
            for(int j = i;j<prices.size();j++)
            {
                int temp = prices[j] - prices[i];
                maxNum = max(temp,maxNum);
            }

        return maxNum;
    }

122. 买卖股票的最佳时机 II(交易无数次)

  • 输入: [7,1,5,3,6,4]

  • 输出: 7

  • 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

  • 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

  • 1.贪心算法，有的赚就卖

  • 2.动态规划dp [len][ 2 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int maxProfit(vector<int>& prices) {
	if (prices.size() < 2)
		return 0;
	int len = prices.size();
	vector<vector<int>>dp(len, vector<int>(2, 0));

	//第一天
	dp[0][0] = 0;          //不持有股票时候：收益
	dp[0][1] = -prices[0];  //  持有股票时候：收益

	//第二天
	for (int i = 1; i < len; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		//还是不持有，卖了今天的股票              
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
		//还是不卖     买今天的股票
	}
	return dp[len - 1][0];
}

//贪心算法
int maxProfit(vector<int>& prices) {
	// write code here
	int res = 0;
	int minn = prices[0];
	for (int i = 1; i < prices.size(); i++)
		res += max(0, prices[i] - prices[i-1]);

	return res;
}

123. 买卖股票的最佳时机 II(交易两次)

  • 输入: [7,1,5,3,6,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
	int firstBuy = INT_MIN;
	int firstSell = 0;
	int secondBuy = INT_MIN;
	int secondSell = 0;
	for (auto it : prices) {
		firstBuy = max(firstBuy, -it);
		firstSell = max(firstSell, firstBuy + it);

		secondBuy = max(secondBuy, firstSell - it);
		secondSell = max(secondSell, secondBuy + it);
	}
	return secondSell;

}
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/08/24/LeetCode-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！