苏州企业网站制作,抖音seo培训,免费在线观看电影大全,百度移动排名优化软件动态规划
1、动态规划的概念 简称DP，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。 简单来说，就是给定一个问题，把它拆成一个个子问题，查到子问题可以直接解决。然后把子问题答案保存起来，以减少重复计算…动态规划
1、动态规划的概念 简称DP，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。 简单来说，就是给定一个问题，把它拆成一个个子问题，查到子问题可以直接解决。然后把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。 核心思想：在于拆分子问题，记住过往，减少重复计算。 2、动态规划的步骤
划分子问题状态表示，一般用数组dp[i]表示当前状态状态转移，即当前状态是由前面那些状态转移过来的，例如dp[i]=dp[i-1]，表示当前状态可以由上一个状态转移过来确定边界，确定初始状态一、线性DP
1、线性DP的概念 动态规划中的一类问题，指状态之间有线性关系的动态规划问题。所谓线性DP，就是递推方程是有一个明显的线性关系的，一维线性和二维线性都有可能。在求的时候，一行一行地来求。
例题----取钱
https://www.lanqiao.cn/problems/3297/learning/ 黄开的银行最近又发行了一种新面额的钞票面值为4，所以现在黄有5种面额的钞票，分别是20，10，5，4，1。但是不变的是他小气，现在又有很多人来取钱，黄又不开心了，请人来取钱，黄又不开心了，请你算出每个来取钱的人黄应该给他至少多少张钞票。
输入格式：每个测评数据含有不超过10组输入，每组给出一个n(1=n=10000)，n为要取出的金额。
输出格式：每组样例输出一个答案(钞票数)。
示例：20 1 2 2 6 2 提示： 设置dp[i]数组 取出金额为i 最小钞票数 转移方程为：dp[i]=Math.min(dp[i-1],dp[i-4],dp[i-5],dp[i-10],dp[i-20])+1 import java.util.Arrays;
import java.util.Scanner;public class Main {
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = { 1, 4, 5, 10, 20 };int[] dp = new int[10001]; // 索引为金额, 值为方案数Arrays.fill(dp, 10000);dp[0] = 0; // 0金额的可选方案数量为0个for (int i = 1; i dp.length; ++i) { // 枚举子问题金额数for (int j : arr) { // 每个子问题可选方案if (i = j) { // 当金额大于等于面额时dp[i] = Math.min(dp[i - j] + 1, dp[i]); // 选择当前面额后 +1，且寻找剩余金额时方案数累加，与当前j之后的面额继续对比方案数}}}while (sc.hasNext()) {System.out.println(dp[sc.nextInt()]);}}
}
例题---破损的楼梯
https://www.lanqiao.cn/problems/3367/learning/ 小蓝来到了一座高耸的楼提前，楼梯共有N级台阶，从第0级台阶出发。小蓝每次可以迈上1级或2级台阶。但是，楼梯上的第级，第级，第级，以此类推，共m级台阶的台阶面已经坏了，不能踩上去。 现在，小蓝想要到达楼梯的顶端，也就是第N级台阶，但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数？由于方案数很大，请输入其对+7取模的结果。
输入格式：
第一行包含两个正整数N(1=N=)和M(0=M=N)，表示楼梯的总级数和坏了的台阶数。 接下来一行，包含M个正整数
