算法汇总啊

一些常用算法汇总

• 算法思想-----数据结构
• 动态规划(DP)
• • 0.题目特点
  • 1.【重点】经典例题(简单一维dp）
  • • 1.斐波那契数列
    • 2.矩形覆盖
    • 3.跳台阶
    • 4.变态跳台阶
    • 2.我的日常练习汇总(DP)
    • • 1.蓝桥真题-----路径

        算法思想-----数据结构

        • 数据结构的存储方式 : 顺序存储(数组) , 链式存储(链表)

            顺序存储(数组) : 在内存中的存储空间是连续的 , 所以可以通过索引来获取存储的元素
            链式存储(链表) : 不是连续存储的 , 可能是这一个那一个的 .
            				 通常是由 数据域和指针域组成-->也就是data和next指针 (next指针指向下一个节点的地址)
          

        • 数据结构底层逻辑

          

            所以啊 , 数据结构的那些东西(数组,链表,栈,队列,图,树,散列表等等)--->其实底层逻辑 都是数组或链表
          

        • 数组和链表优缺点

          数组--->可以随机访问(通过索引) , 但是 需要考虑存储容量的问题
          链表--->没有存储容量的问题 , 但是不能随机访问元素
          

        • 数据结构存在的意义

            数据结构存在的意义---->就是为了处理数据啊(增删改查)--->怎么增删改查呢?---->遍历+递归
            那为什么会有那么多种数据结构呢 ? ---->因为每种数据结构的应用场景不一样(灵活应用,优化代码嘛) 
          

          动态规划(DP)

          0.题目特点

          • 1.计数（问：how many ways。。。）
            • a.有多少种方式 走到右下角
            • b.有多少种方法 选出k个数使得和是sum
            • 2.求最大值、最小值（最大的一个解题类型）
              • a.从左上角走到右下角 路径的最大数字和
              • b.最长上升子序列的长度
              • 3.求存在性
                • a.取石子游戏，先手是否必胜
                • b.能不能选出k个数 使得和是sum

                  1.【重点】经典例题(简单一维dp）

                  1.斐波那契数列

                  1 1 2 3 5 8 …

                  这是最经典的递归问题，

                  但 如果用递归求解，会重复计算一些子问题。

                  那如何用 动态规划 求解呢。

                  题目描述：求斐波那契数列的第n项，n if(n if(n //计算顺序 fib[i] = fib[i-1] + fib[n-2]; //状态方程 return fib[n]; } if(n if(n dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } if(n dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } int[] dp = new int[n+1]; Arrays.fill(dp,1); //把dp数组中所有元素初始化为1 //对于每一级台阶，方案数都是前面所有台阶的方案数的和 for(int i=1;i for(int j=1;j dp[i] += dp[j]; } } return dp[n]; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此输入您的代码... //最短路径--dp //最小公倍数 = 两数乘积/最大公约数 System.out.println(check()); scan.close(); } public static int check(){ int[] dp = new int[2021+1]; //结束条件 //初始化 Arrays.fill(dp,Integer.MAX_VALUE); dp[1] = 0; dp[2] = 2; for(int i=3;i for(int x=i-21;x if(x if(b == 0) return a; return gcb(b,a%b); } public static int lcm(int a,int b,int gcb){ return (a*b)/gcb; } }