动态规划/贪心算法

一、动态规划

动态规划 是一种用于解决优化问题的算法设计技术，尤其适用于具有重叠子问题和最优子结构性质的问题。它通过将复杂问题分解为更简单的子问题，并保存这些子问题的解以避免重复计算，从而提高效率。

动态规划的核心思想

1. 最优子结构（Optimal Substructure）：

   • 一个问题的最优解可以通过其子问题的最优解来构造。
   • 比如在最短路径问题中，从起点到终点的最短路径可以由起点到某个中间点的最短路径和该中间点到终点的最短路径组合而成。

2. 重叠子问题（Overlapping Subproblems）：

   • 在递归求解过程中，相同的子问题会被多次求解。
   • 动态规划通过存储子问题的解来避免重复计算，通常使用数组或哈希表等数据结构来存储这些解。

1.算法原理

1)状态表示

dp表(一维数组  填满该表其中某一个值就是结果 数组中某个数据值的意义就是状态表示)

通过题目要求 经验  分析问题发现重复子问题 来创建dp表

2)状态转移方程

dp[i]等于什么?

3)初始化

根据状态转移方程填表,保证填表的时候不越界

4)填表顺序

为了填写当前状态的时候,所需要的状态已经计算过了

5)返回值

题目要求+状态表示

2.例题

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：输入：n = 4 输出：4    解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

状态表示:dp[i]第i个泰波那契数的值

状态转移方程:dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

初始化:dp[0]=0;dp[1]=1;dp[2]=1

填表顺序:从左向右

返回值:dp[n]

JAVA代码

class Solution {public int tribonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
int[] dp=new int[n+1];
dp[0]=0;dp[1]=1;dp[2]=1;
for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
return dp[n];}
}

3.空间优化

求解某个状态时仅需要其的前几个状态

一定要确定好赋序

int tribonacci(int n){
//空间优化 滚动数组
if(n==0) return 0;
if(n==1||n==2) return 1;
int a=0;int b=1,c=1;int d=0;
for(int i=3;i<=n;i++){d=a+b+c;a=b;b=c;c=d;}
return d;
}

 二、贪心算法

1.算法原理:

局部最优->全局最优

把解决问题的过程分为若干步,解决每一步的时候都选择当前看起来最优的解法

希望得到全局最优解

但贪心算法并不总是保证全局最优解

2.例题

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

示例 1：

[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

在数组中挑出两个数,使其差值最大

1)暴力解法(两层for循环) 超出时间限制时间复杂度O(n^2)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;class Solution {public int maxProfit(int[] prices) {int ret = 0;if (prices == null || prices.length < 2) {return 0;}for (int i = 0; i < prices.length - 1; i++) {for (int j = i+1; j < prices.length; j++) {ret = Math.max(ret, prices[j] - prices[i]);}}return ret;}public static void main(String[] args) {Scanner sc=new Scanner(System.in);Solution solution=new Solution();List<Integer> pricesList = new ArrayList<>();while (sc.hasNextInt()) {pricesList.add(sc.nextInt());}int[] prices = new int[pricesList.size()];for (int i = 0; i < pricesList.size(); i++) {prices[i] = pricesList.get(i);}int ret=solution.maxProfit(prices);System.out.println(ret);sc.close();}
}//在输入结束后输入一个非数字字符（如字母 'q'），这样 hasNextInt() 会返回 false，从而结束循环,或 Ctrl + Z（Windows）来发送 EOF 信号。

2)贪心

分为两段,prevmin表示前一段中最小值(买入),prices[i]卖出去的价钱

class Solution {public int maxProfit(int[] prices) {int ret=0;for(int i=0,prevmin=Integer.MAX_VALUE;i<prices.length;i++){ret=Math.max(ret,prices[i]-prevmin);prevmin=Math.min(prevmin,prices[i]);}return ret;}
}

三、 (双指针算法)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

数组划分

利用数组下标充当指针 

两个指针的作用:

cur:从左往右扫描,遍历数组

dest:已处理的区间内,非0元素的最后一个位置

三个区间:

[0,dest]   [dest+1,cur-1]  [cur,n-1]

非0         0元素                 待处理的区间

解法:

初始dest=-1 cur=0

遇到0元素,cur++;

遇到非0元素 swap(dest+1,cur)交换位置 dest++ cur++

class Solution {public void moveZeroes(int[] nums) {
int dest=-1;
int cur=0;
int k=0;
int n=nums.length;
while(cur<n){
if(nums[cur]==0)
cur++;
else
{dest++;
k=nums[dest];
nums[dest]=nums[cur];
nums[cur]=k;
cur++;
}}}
}

 

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

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

利用数组下标充当指针(i,j)

class Solution {public int maxProfit(int[] prices) {//双指针算法int ret=0;int i=0,j=0;for(i=0;i<prices.length;i++){j=i;while(j+1<prices.length && prices[j+1]-prices[j]>0){j++;}ret+=prices[j]-prices[i];i=j;}return ret;}
}

四、递归

1.什么是递归

函数自己调用自己(主问题->相同的子问题)

出口(一个问题不能在分割了)           

1.算法思想

函数头 函数体 递归出口

把递归的函数当成一个黑盒,不在意递归的细节

深度优先遍历(后序遍历)

2.例题

计算布尔二叉树的值

给你一棵 完整二叉树 的根，这棵树有以下特征：

• 叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
• 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算 一个节点的值方式如下：

• 如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
• 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。

返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

class Solution {public boolean evaluateTree(TreeNode root) {if(root.left==null) return root.val==0 ? false: true;boolean left=evaluateTree(root.left);boolean right=evaluateTree(root.right);return root.val==2 ?left | right : left & right;}
}