您现在的位置是:首页 > 正文

2_5_LeetCode刷题总结(基本算法)动态规划

2024-02-01 05:02:21阅读 2

编程总结

简介动态规划 (Dynamic Programic) 是计算机科学领域的一个概念,它是一种特殊的分治思想,利用它可以实现时间复杂度的优化。Dynamic 动态,即会变化的;Programming 应理解为「表格法」。
合起来动态规划就是用一张可变的表格来存储运算结果。在不定义状态及阶段等概念的情形下解释动态规划

举一个例子_背包问题

在这里插入图片描述

简单算法

在这里插入图片描述
在这里插入图片描述

动态规划

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

62. 不同路径

在这里插入图片描述
在这里插入图片描述
1. 穷举分析
在这里插入图片描述
2. 确定边界
在这里插入图片描述
3. 找出规律,确定最优子结构
在这里插入图片描述
4. 写出状态转移方程
在这里插入图片描述
5. 代码实现

int uniquePaths(int m, int n)
{
	int **dp = (int **)malloc(sizeof(int *) * m);
	for (int i = 0; i < m; i++) {
		dp[i] = (int *)malloc(sizeof(int) * n);
	}
	// 初始化
	for (int i = 0; i < m; ++i) {
		dp[i][0] = 1;
	}
	for (int j = 0; j < n; ++j) {
		dp[0][j] = 1;
	}
	for (int i = 1; i < m; ++i) {
		for (int j = 1; j < n; ++j) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}

	return dp[m - 1][n - 1];
}

121. 买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
在这里插入图片描述

dp[i] 表示前 i 天的最大利润,我们需要始终保持利润最大化

int maxProfit(int *prices, int pricesSize) {
	int len = sizeof(prices)/sizeof(int *);
	int dp[100000] = { 0 };
	int minprices = prices[0];
	int i = 0;
		
	if (pricesSize == 0) {
		return 0;
	}

	for (i = 1; i < pricesSize; i++) {
		minprices = min(minprices, prices[i]); // 维持谷值
		dp[i] = max(dp[i-1], prices[i] - minprices); // 方程,当天出售的话和不出售取最大值为当前能获得最大的利润
	}

	return dp[i -1];
}

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

1)递归调用的思路:
在这里插入图片描述
2)记忆化搜索
以递归思路为基础,递归有的是不必要的,因而进行了一些减递归操作。
在这里插入图片描述
3)动态规划思路(由小至大):
在这里插入图片描述

三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

// 记忆化搜索
int waysToStep2(int n)
{
	if (n <= 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	} else if (n == 2) {
		return 2;
	} else if (n == 3) {
		return 4;
	}
	if (memo[n] == 0) {
		memo[n] = (waysToStep2(n-1)%1000000007 + waysToStep2(n-2)%1000000007 + waysToStep2(n-3)%1000000007)%1000000007;
	}
	printf("memo[%d] = %d\n", n, memo[n]);
	return memo[n];
}

#define MOD_NUM 1000000007
// 动态规划
int waysToStep(int n)
{
	memo[0] = 1;
	memo[1] = 1;
	memo[2] = 2;
	memo[3] = 4;
	for (int i = 3; i <= n; i++) {
		memo[i] = ((memo[i-1]%MOD_NUM + memo[i-2]%MOD_NUM)%MOD_NUM + memo[i-3]%MOD_NUM)%MOD_NUM;
	}

	printf("memo[%d] = %d\n", n, memo[n]);
	return memo[n];
}
int climbStairs(int n){
    //f(x) = f(x-1) + f(x-2) 
    if (n <= 1){//第0阶和第1阶只有一种方法
        return 1;
    }
    int way;
    int memo[2] = {1,1};
    for (int i = 2; i <= n; ++i) {
        //上楼梯->从第2阶楼梯开始
        way = memo[0] + memo[1];
        memo[0] = memo[1];
        memo[1] = way;
    }
    return way;
}

1025.爱丽丝和鲍勃一起玩游戏

他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:
选出任一 x,满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 False。假设两个玩家都以最佳状态参与游戏。

bool divisorGame(int N){
    bool dp[1001];
    dp[1]=false;
    dp[2]=true;

    for(int i=3;i<=N;i++)
    {
        dp[i]=false;
        for(int j=1;j<i;j++)          //内层循环,此时i即为被除数n,j为除数k
            if((dp[i-j]==false)&&(i%j==0))
            {
                dp[i]=true;
                break;
            }
    }
                 
    return dp[N];            
}

事实上,N为偶数就是爱丽丝赢,为奇数就是鲍勃赢。
n=1时,先走输;
n=2时,先走赢;
这些先存进dp数组里,代表子问题的最优解。

n=3之后,先走的如果想赢(爱丽丝如果想赢),就需要找到小于n的数k,能使得在符合条件(n%k==0)的基础上还能让n-k(下一局的n)是先走输。(即n-k的最优解是输,即下一局的人再怎么聪明也是输。)

即在内层循环中如果找到一个数使得if((dp[i-j]false)&&(i%j0)),那么该数是先走赢,一层循环走下来找不到这么一个数的话,那么该数是先走输。故只要找到一个符合条件就可以直接跳出循环了

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

动态规划,就是第i个元素最大值memo[i],取决于前memo[i-1]是否加nums[i],如果加了大些,就变成了 memo[i-1]+nums[i], 否则不加,那断开之前的联系,就是nums[i]的值。

再利用一个小技巧,下面的表达式,当memo[i-1] 大于0时,(此时memo[i-1] + nums[i] 一定大于 nums[i]))就加,否则就不加。
memo[i] = fmax(memo[i-1] + nums[i], nums[i]);

53. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
>

// 状态转移方程:f(i)=max{f(i−1)+nums[i],nums[i]}
int maxSubArray(int* nums, int numsSize)
{
    if (numsSize == 1)
	{
		return nums[0];
	}
    int *memo = malloc(sizeof(int)*numsSize);
    memo[0] = nums[0];
    int max = nums[0];
    for(int i = 1; i < numsSize; i++)
	{
        memo[i] = fmax(memo[i-1] + nums[i], nums[i]);
        max = fmax(max, memo[i]);
    }

    return max;
}

股票买卖

121. 买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

只能买入一次,卖出一次

在这里插入图片描述

int maxProfit(int *prices, int pricesSize) 
{
	int len = sizeof(prices)/sizeof(int *);
	int dp[1000000] = { 0 };
	int minprices = prices[0];
	int i = 0;
		
	if (pricesSize == 0) {
		return 0;
	}
	for (i = 1; i < pricesSize; i++) {
		minprices = fmin(minprices, prices[i]);
		dp[i] = fmax(dp[i-1], prices[i] - minprices);
	}

	return dp[i -1];
}

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。

可以多次买入,多次卖出
在这里插入图片描述

int maxProfit(int *prices, int pricesSize) {
    int i = 0;
    int profit = 0;

    if (pricesSize == 0) {
        return 0;
    }
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > prices[i-1]) {
            profit = profit + prices[i] - prices[i-1];
        }
    }

    return profit;
}

123. 买卖股票的最佳时机 III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

最多参与两笔交易

在这里插入图片描述

int maxProfit(int* prices, int pricesSize) {
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    for (int i = 1; i < pricesSize; ++i) {
        buy1  = fmax(buy1, -prices[i]);
        sell1 = fmax(sell1, buy1 + prices[i]);
        buy2  = fmax(buy2, sell1 - prices[i]);
        sell2 = fmax(sell2, buy2 + prices[i]);
    }
    return sell2;
}

309. 最佳买卖股票时机含冷冻期

卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)
在这里插入图片描述

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) {
        return 0;
    }

    // f[i][0]: 手上持有股票的最大收益
    // f[i][1]: 手上不持有股票,并且处于冷冻期中的累计最大收益
    // f[i][2]: 手上不持有股票,并且不在冷冻期中的累计最大收益
    int f[pricesSize][3];
    f[0][0] = -prices[0];
    f[0][1] = f[0][2] = 0;
    for (int i = 1; i < pricesSize; ++i) {
        f[i][0] = fmax(f[i - 1][0], f[i - 1][2] - prices[i]);
        f[i][1] = f[i - 1][0] + prices[i];
        f[i][2] = fmax(f[i - 1][1], f[i - 1][2]);
    }
    return fmax(f[pricesSize - 1][1], f[pricesSize - 1][2]);
}

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
在这里插入图片描述

int maxProfit(int* prices, int pricesSize, int fee){
    int dp[pricesSize][2];
    dp[0][0] = 0, dp[0][1] = -prices[0];
    for (int i = 1; i < pricesSize; ++i) {
        dp[i][0] = fmax(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = fmax(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[pricesSize - 1][0];
}

打家劫舍

198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

在这里插入图片描述

int rob(int *nums, int numsSize) {
    if (numsSize == 1) {
        return nums[0];
    }
    int dp[numsSize+1];
    dp[0] = nums[0];
    dp[1] = fmax(nums[0], nums[1]);
    for(int i = 2; i < numsSize; i++) {
        // 偷窃第k间房屋,那么就不能偷窃第k−1间房屋,总金额为前k−2间房屋的最高总金额与第k间房屋的金额之和
        // 不偷窃第k间房屋,偷窃总金额为前k−1间房屋的最高总金额
        dp[i] = fmax(dp[i-2] + nums[i], dp[i-1]);
    }

    return dp[numsSize - 1];
}

213. 打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

这道题中的房屋是首尾相连的,第一间房屋和最后一间房屋相邻,因此第一间房屋和最后一间房屋不能在同一晚上偷窃

在这里插入图片描述

int robRange(int *nums, int start, int end) 
{
    int first = nums[start], second = fmax(nums[start], nums[start + 1]);
    for (int i = start + 2; i <= end; i++) {
        int temp = second;
        second = fmax(first + nums[i], second);
        first = temp;
    }
    
    return second;
}

int rob(int *nums, int numsSize) 
{
    if (numsSize == 1) {
        return nums[0];
    } else if (numsSize == 2) {
        return fmax(nums[0], nums[1]);
    }
    
    return fmax(robRange(nums, 0, numsSize - 2), robRange(nums, 1, numsSize - 1));
}

337. 打家劫舍 III

在这里插入图片描述

struct SubtreeStatus {
    int selected;
    int notSelected;
};

struct SubtreeStatus dfs(struct TreeNode *node) {
    if (!node) {
        return (struct SubtreeStatus){0, 0};
    }
    struct SubtreeStatus l = dfs(node->left);
    struct SubtreeStatus r = dfs(node->right);
    int selected    = node->val + l.notSelected + r.notSelected;
    int notSelected = fmax(l.selected, l.notSelected) + fmax(r.selected, r.notSelected);
    return (struct SubtreeStatus){selected, notSelected};
}

int rob(struct TreeNode *root) 
{
    struct SubtreeStatus rootStatus = dfs(root);
    return fmax(rootStatus.selected, rootStatus.notSelected);
}

139.单词拆分

在这里插入图片描述
在这里插入图片描述

#define NUM_100 100

unsigned long long Hash(char *s, int l, int r) 
{
	unsigned long long value = 0;
	for (int i = l; i < r; i++) {
		value = value * NUM_100;
		value += s[i] - 'a' + 1;
	}
	return value;
}

bool query(unsigned long *rec, int len_rec, unsigned long x) 
{
	for (int i = 0; i < len_rec; i++) {
		if (rec[i] == x) return true;
	}
	return false;
}

bool wordBreak(char *s, char** wordDict, int wordDictSize) 
{
	unsigned long *rec = (unsigned long *)malloc(sizeof(unsigned long *) * wordDictSize + 1);
	int len_s = strlen(s);
	bool *dp = (bool *)malloc(len_s + 1);
	int i, j;

	for (int i = 0; i < wordDictSize; i++) {
		rec[i] = Hash(wordDict[i], 0, strlen(wordDict[i]));
	}
	memset(dp, 0, (len_s + 1));
	dp[0] = true;
	for (i = 1; i <= len_s; i++) {
		for (j = 0; j < i; j++) {
			if (dp[j] && query(rec, wordDictSize, Hash(s, j, i))) {
				dp[i] = true;
				break;
			}
		}
	}

	return dp[len_s];
}

网站文章

  • 浅显易懂的《C++类和对象》-中篇

    内容充实、概念易懂,C++类和对象中篇,类的6个默认成员函数,轻松掌握。

    2024-02-01 05:01:51
  • 「Active Directory Sec」白银票据和黄金票据

    「Active Directory Sec」白银票据和黄金票据

    白银票据: 即伪造的TGS。当获取需要访问的目标服务器NTLM HASH后,就可以利用Mimikatz伪造TGS,直接去访问目标服务器。此过程不需要KDC的参与。但缺点是只能访问一个服务。黄金票据: ...

    2024-02-01 05:01:44
  • Day3.数据可视化-- 可视化基础

    Day3.数据可视化-- 可视化基础

    可视化主要是以图像来展示数据间的关系,常见的图形种类有折线图,散点图,条形图,直方图,饼图。此外在接下来课程中还会用到箱线图,热力图,蜘蛛图,表示二元变量分布和成对关系的视图。学好可视化...

    2024-02-01 05:01:37
  • C++ 内存分区: 代码区 全局区 栈区 堆区

    C++ 内存分区: 代码区 全局区 栈区 堆区

    1.代码区: 存放函数体的二进制代码,由操作系统进行管理 **2.全局区:**存放全局变量和静态变量以及常量,数据在程序结束后由操作系统释放 存放内容:全局变量、静态变量、常量区(字符串常量和其他常量) **3.栈区:**由编译器分配和释放,存放函数的参数值,局部变量等 **4.堆区:**由程序员分配和释放,若程序员不释放,程序结束时由操作系统回收 ...

    2024-02-01 05:01:10
  • Android中 Bitmap Drawable Paint的获取、转换以及使用

    比如Drawable中有一系列连续的图片,img_0.png, img_1.png, img_2.png ... 如果要动态获取这些图片,通过&quot;R.drawable.img_x&quot;的...

    2024-02-01 05:01:03
  • 【靶场平台】一些免费好用的靶机渗透测试环境

    1、Vulhub: (各种漏洞环境集合,一键搭建漏洞测试靶场) https://vulhub.org/(在线版) https://github.com/vulhub/vulhub(离线版) 2、Vul...

    2024-02-01 05:00:55
  • Servlet的自动加载

    Servlet的自动加载

    本文阐述了Servlet中与自动加载相关的知识点,并展示了怎样通过设置loadOnStartup属性将自定义Servlet设定为自动加载。

    2024-02-01 05:00:27
  • STM32单片机-CorTexM3位带操作的理解

    STM32单片机-CorTexM3位带操作的理解

    STM32单片机-CorTexM3位带操作的理解

    2024-02-01 05:00:21
  • 测试人员要掌握的基本的SQL语句

    测试人员要掌握的基本的SQL语句

    目录  一、DDL—数据定义语言(CREATE,ALTER,DROP,DECLARE)  二、DML—数据操纵语言(SELECT,DELETE,UPDATE,INSERT)  三、DCL—数据控制语言(GRANT,REVOKE) 四、下半部分内容(主要是PL/<span class="t_tag" onclick="function onclick(){tagshow(event)}"

    2024-02-01 05:00:15
  • vue关于@无法找到文件报错

    vue关于@无法找到文件报错

    如果在Vite项目中使用@无法找到文件,通常是因为未正确配置路径别名(path alias)导致的。在Vite中,您可以使用vite.config.js文件来配置路径别名。请确保将路径别名配置为与您的项目结构和实际路径相匹配。在上述示例中,我们使用alias选项来配置路径别名。通过@别名,我们将./src目录与@关联起来。//配置less @ 跨域。

    2024-02-01 05:00:10