当前位置： 首页 > article >正文

复习动态规划入门

article 2025/1/27 4:03:28

题目：

最小花费爬楼梯

暴力：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int dfs(int x)
{
	if(x == 0 || x == 1)
	return 0;
	else
	return min(dfs(x-1) + cost[x-1],dfs(x-2) + cost[x-2]);
}
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++)
	cin >> cost[i];
	cout << dfs(n);
	return 0; 
}

记忆化搜索：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int mem[N];//到达第i层之前最小花费 
int dfs(int x)
{
	int sum = 0;
	if(mem[x])
	return mem[x]; 
	if(x == 0 || x == 1)
	return 0;
	else
	sum = min(dfs(x-1) + cost[x-1],dfs(x-2) + cost[x-2]);
	mem[x] = sum;
	return sum;
}
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++)
	cin >> cost[i];
	cout << dfs(n);
	return 0; 
}

dp1：

dp定义到达第i层前最小花费

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int f[N];//到达第i层最小花费 
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++)
	cin >> cost[i];
	f[0] = f[1] = 0;
	for(int i = 2 ; i <= n ; i++)
	{
		f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
	}
	//cout << f[n];
	for(int i = 0 ; i <= n ; i++)
	cout <<f[i] << " "; 
	return 0; 
}

dp2：

dp定义到达第i层的最小花费

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int f[N];//到达第i层最小花费 
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++)
	cin >> cost[i];
	f[0] = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
	}
	cout << f[n];
/*	for(int i = 0 ; i <= n ; i++)
	cout <<f[i] << " "; */
	return 0; 
}

最长递增子序列：
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态

dfs：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int f[N];
int dfs(int x)
{
	int sum = 1;
	for(int i = 1 ; i < x ; i++)//注意是＜ 
	{
		if(arr[i] < arr[x])
		{
			sum = max(sum,dfs(i) + 1);
		}
	}
	return sum;
}
int main()
{
	int ans = -1;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	for(int i = 1 ; i <= n ; i++)
	{
		ans = max(ans,dfs(i));
	} 
	cout << ans; 
	return 0; 
}

记忆化搜索：
 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int mem[N];//存的是以i为结尾最长上升子序列的最大值 
int dfs(int x)
{
	int sum = 1;
	if(mem[x])
	return mem[x]; 
	for(int i = 1 ; i < x ; i++)//注意是＜ 
	{
		if(arr[i] < arr[x])
		{
			sum = max(sum,dfs(i) + 1);
		}
	}
	mem[x] = sum;
	return sum;
}
int main()
{
	int ans = -1;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	for(int i = 1 ; i <= n ; i++)
	{
		ans = max(ans,dfs(i));
	} 
	cout << ans; 
	return 0; 
}

dp：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int f[N];//存的是以i为结尾最长上升子序列的最大值 

int main()
{
	int ans = -1;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> arr[i];
		f[i] = 1;		
	}

	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j < i ; j++)
		{
			if(arr[j] < arr[i])
			{
				f[i] = max(f[i],f[j] + 1);
			}
		}
	} 
	for(int i = 1 ; i <= n ; i++)
	ans = max(ans,f[i]);
	cout << ans; 
	return 0; 
}

零钱兑换

B3635 硬币问题 - 洛谷 | 计算机科学教育新生态

记忆化搜索：
 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int len = 0;
int arr[10] = {1,5,11};
int mem[N];
int dfs(int x)
{
	int sum = 1e9;
	if(mem[x])
	return mem[x];
 	if(x == 0 || x < 0)
 	return 0;
 	for(int i = 0 ; i < 3 ; i++)
 	{
 		if(arr[i] <= x)
 		{
 			sum = min(sum,dfs(x - arr[i]) + 1);
		}
	 }
	 mem[x] = sum;
	 return sum;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x;
	cin >> n;
	cout << dfs(n); 
	return 0;
}

dp：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int n;
int arr[10] = {1, 5, 11};
int f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    f[i] = 1e9;
    for (int i = 0; i <= n; ++i) 
	{
        for (int j = 0; j < 3; ++j)
		 {
            if (i >= arr[j])
			{
                f[i] = min(f[i], f[i - arr[j]] + 1);
            }
        }
    }

    if (f[n] == 1e9) 
	{
        cout << -1; 
    } 
	else 
	{
        cout << f[n];
    }

    return 0;
}

连续子数组的最大和：

贪心：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int main() 
{
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	int ans = -1e9,sum = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		if(sum < 0)
		sum = 0;
		sum += arr[i];
		ans = max(ans,sum);
	}
	cout << ans;
    return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

  1. 局部最优到全局最优的转换：Kadane's Algorithm通过维护一个当前子数组的最大和（sum）和一个全局最大和（ans），在遍历数组时，如果当前子数组的和变为负数，则重新开始计算新的子数组和（即重置sum为0）。这种方法确保了每一步都是在尝试找到以当前元素为结尾的子数组中的最大和。由于我们总是在更新ans为遇到的最大子数组和，因此当遍历结束时，ans就是全局最大子数组和。

  2. 无需回溯：与动态规划等方法不同，Kadane's Algorithm不需要回溯或存储中间状态。它只依赖于当前遍历到的元素和之前的累积和，这使得算法非常高效，时间复杂度为O(n)。

  3. 贪心选择的正确性：在这个特定问题中，贪心选择的正确性在于我们总是尝试扩展当前子数组（只要它的和仍然是非负的），或者当遇到一个使当前子数组和变为负数的元素时，我们重新开始一个新的子数组。这种方法确保了我们不会错过任何可能构成全局最大子数组的部分。

  4. 问题的特定结构：最大子数组和问题具有一种特殊结构，使得局部最优解（以当前元素为结尾的最大子数组和）能够直接导向全局最优解（整个数组中的最大子数组和）。这种结构是贪心算法能够成功应用的关键。

暴力dfs：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int dfs(int x)
{
	if(x == 0)
	return 0;
	int sum = -1e9;
	sum = max(arr[x],dfs(x - 1) + arr[x]);

	return sum;
}
int main() 
{
	int ans = -1e9;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	
	for(int i = 1 ; i <= n ; i++)
	{
		ans = max(ans,dfs(i));
	}
	cout << ans;
    return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

记忆化搜索：
 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int mem[N]; 
int dfs(int x)
{
	if(mem[x])
	return mem[x];
	if(x == 0)
	return 0;
	int sum = -1e9;
	sum = max(arr[x],dfs(x - 1) + arr[x]);
	mem[x] = sum;
	return sum;
}
int main() 
{
	int ans = -1e9;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	
	for(int i = 1 ; i <= n ; i++)
	{
		ans = max(ans,dfs(i));
	}
	cout << ans;
    return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

动态规划：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int f[N]; 
/*int dfs(int x)
{
	if(mem[x])
	return mem[x];
	if(x == 0)
	return 0;
	int sum = -1e9;
	sum = max(arr[x],dfs(x - 1) + arr[x]);
	mem[x] = sum;
	return sum;
}*/
int main() 
{
	int ans = -1e9;
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	cin >> arr[i];
	
	for(int i = 1 ; i <= n ; i++)
	{
		f[i] = max(f[i] , f[i-1] + arr[i]);
	}
	for(int i = 1 ; i <= n ; i++)
	{
		if(ans < f[i])
		ans = f[i];
	}
	cout << ans;
    return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/


http://www.kler.cn/a/517849.html

相关文章：

  • 笔灵ai写作技术浅析（一）
  • 第二十一周：Mask R-CNN
  • Mono里运行C#脚本36—加载C#类定义的成员变量和方法的数量
  • 飞牛NAS新增虚拟机功能，如果使用虚拟机网卡直通安装ikuai软路由（如何解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题）
  • vue3 获取百度天气
  • Windows系统Tai时长统计工具的使用体验
  • 龙蜥社区加入智算产业联盟，助力构建开放、包容、普惠的 AI 新生态
  • 【含开题报告+文档+PPT+源码】基于java web的篮球馆管理系统系统的设计与实现
  • 计算机网络 （58）无线局域网WLAN
  • 综合能源规划仿真软件
  • 【负载均衡式在线OJ】加载题目信息（文件版）
  • WinDBG查找C++句柄泄露
  • 剑指Offer|LCR 044.在每个树行中找最大值
  • 【爬虫开发】爬虫开发从0到1全知识教程第12篇：scrapy爬虫框架,介绍【附代码文档】
  • mysql 学习3 SQL语句--整体概述。SQL通用语法；DDL创建数据库，查看当前数据库是那个，删除数据库，使用数据库；查看当前数据库有哪些表
  • 小南每日 AI 资讯 | 2025年AI泡沫破裂？ | 25/01/24
  • uart iic spi三种总线的用法
  • JRE、JVM 和 JDK 的区别
  • 网安加·百家讲坛 | 樊山：数据安全之威胁建模
  • elasticsearch 使用from+size深度分页性能问题解决方案
  • 数据库管理-第287期 Oracle DB 23.7新特性一览（20250124）
  • 【JAVA】获取windows内存使用率排名前十的进程信息、总的cpu和内存使用率
  • iOS swift 后台运行应用尝试失败
  • 第84期 | GPTSecurity周报
  • 2025年01月23日Github流行趋势
  • 日常梳理-网络架构