当前位置:   article > 正文

【算法】05 动态规划_小团在一个n*m的网格地图上探索。 网格地图上第i行第j列的格子用坐标(i,j)简

小团在一个n*m的网格地图上探索。 网格地图上第i行第j列的格子用坐标(i,j)简

概念

  1. 重叠子问题:动态规划用于当相同的子问题的解决方案被重复利用的情况。在动态规划中,子问题解决方案被存储在一个表中,因此不必重新计算。即:如果这个问题没有重叠子问题, 动态规划是没有用的。
  2. 最优子结构:如果问题的一个最优解包含了子问题的最优解,则该问题具有最优子结构。当一个问题具有最优子结构的时候,我们就可能要用到动态规划。
  3. 自底向上:动态规划的基本思想是将原问题拆分为若干子问题,自底向上地求解。
  4. 自顶向下:备忘录方法,维护一个记录子问题的解的表。

找零问题

假设货币面额有1,2,4,5,10,每种数量都无限多,现在给出金额n(1<=n<=100000),求出最少使用多少张货币。

此时则不可以用贪心算法,而是应该用动态规划。因为此时前n-1项之和不再小于第n项的值,所以贪心不再成立。例如:8元如果用贪心查找,每次都选最大的,那我们找不到解,而实际上可以用两张4元就可以解决。

int main() {
   
	vector<int> v = {
   1,2,4,5,10};
	int n;
	cin >> n;
	int dp[n+1];
	for(int i = 0; i <= n; i++){
   
		dp[i] = i;	// 初始化为i。任意金额都可以由一元组成
	}
	for(int i = 0; i < v.size(); i++){
   
		dp[v[i]]= 1;	// 如果当前金额为现有货币币种,那一张就够。
	}
	for(int i = 1; i <= n; i++){
   
		for(int j = 0; j < v.size(); j++){
   
			if(v[j] > i)
				continue;
			dp[i] = min(dp[i], dp[i-v[j]] + 1);	
			// 当前金额i是否可以通过一张面额为v[j]的币种和金额为i-v[j]的数量组成更小的张数。
		}
	}
	cout << dp[n] << endl;
} 
  • 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

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

如果台阶级数大于2,设为n的话,这时我们把n级台阶时的跳法看成n的函数,记为f(n),有:

int jump(int n) {
   
	if (n <= 2)	{
   
		return n;
	} else {
   
		return jump(n-1)+jump(n-2);
	}  
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

int jump2(int n) {
   
    if (n <= 1) {
   
        return 1;
    } else {
   
        return 2 * jump2(n - 1);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

可通过画递归树来求解递归式,得出直接计算的公式。

最长递增/递减子序列

  • dp[i]表示若递增子序列以ai为子序列最后一个元素时它的最长长度。
  • dp[1] = 1
  • dp[x] = max{1, dp[i]+1 | ai<ax && i<x}
// 一般解法

int nums[201];		// 数组
int dp[201];		// dp[i]:以ai结尾的最长子序列长度
int count[201];		// count[i]:以ai结尾的LIS个数

int main() {
   
	int T;
	cin >> T;
	while (T--) {
   
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i) {
   
			cin >> nums[i];
			dp[i] = 1;
			count[i] = 1;
		}
		int max = 1, result = 0;
		for (int i = 1; i <= n; ++i) {
   
			for (int j = 1; j < i; ++j) {
   
				// 不需要求个数
				// if (nums[i] > nums[j] && dp[i] <= dp[j])
				// 	dp[i] = dp[j] + 1;
				
				if (nums[i] > nums[j]) {
   
					if (dp[i] < dp[j] + 1) {
   
						dp[i] = dp[j] + 1;
						count[i] = count[j];
					}
					else if (dp[i] == dp[j] + 1) {
   
						count[i] += count[j];
					}
				}
			}
			if (dp[i] > max) max = dp[i];
		}
		for (int i = 1; i <= n; ++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
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/689971
推荐阅读
相关标签
  

闽ICP备14008679号