LeetCode|Dynamic Programming --- 动态规划刷题(一) 算法|动态规划

文章目录

动态规划
- 动态规划的三特点
- 动态规划的四要素
第一题 : 零钱兑换
- 解题思路:
- 代码实现:
第二题: 跳石板
- 解题思路:
- 代码实现:
第三题: 不同路径
- 解题思路:
- 代码实现:
第四题: 最大子数组和
- 解题思路:
- 代码实现:
第五题: 最小路径和
- 解题思路:
- 代码实现:

动态规划通俗的来说,动态规划就是把大事情化成小事情,小事情变无的思路,
动态规划的三特点

把原来的问题分解成了几个相似的子问题。

所有的子问题都只需要解决一次。

储存子问题的解。

动态规划的四要素

状态定义

状态间的转移方程定义

状态的初始化

返回结果

第一题 : 零钱兑换 Leet Code 322: 零钱兑换
描述:
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的
解题思路:

状态 F(i) : 表示凑成i所需最少的硬币个数

状态转移方程: F(i) = F(coins[j]) + min(F(i-coins[j]))(coins[j[表示已有的硬币)

初始状态: F(0) = 0; F(coins[j]) = 1 (已有的面值可以直接拿,所以是1)

返回结果: F(M) (M表示amount)

LeetCode|Dynamic Programming --- 动态规划刷题(一)

文章图片

代码实现:

class Solution { public int coinChange(int[] coins, int amount) { // 创建一个大小为 amount+1 的数组dp int[] dp = new int[amount+1]; // 将数组初始化为 -1 Arrays.fill(dp,-1); // 将金额零的最小硬币个数改为0 即 dp[0] = 0 dp[0] = 0; // 遍历dp数组,从1下标开始,依次计算金额的最少硬币个数 for(int i = 1; i <= amount; i++) { // 遍历coins数组 for(int j = 0; j < coins.length; j++){ // 面额>=硬币面值当dp[i-coins[j]] == -1时,表示没有与之对应的硬币,也就不能组成总金额 if(coins[j] <= i && dp[i-coins[j]] != -1){ // dp[i] == -1时,表示此时还未计算或dp[i] > 真正在计算的最少硬币个数则需要更新dp[i] if(dp[i] == -1 || dp[i] > dp[i-coins[j]]+1){ dp[i] = dp[i-coins[j]]+1; } }} } return dp[amount]; } }

第二题: 跳石板来源：牛客网跳石板
描述:
小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24： 4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
解题思路:

状态 F(i) : 表示到达i的最小步数

状态转移方程: F(i+j) = min(F(i)+1,F(i+j)) (i表示所在位置,j表示可以跳的步数)

初始状态: F(N) = 0; (N表示起始位置)

返回结果: F(M) (M表示需要到达的石板)

代码实现:

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { // 用ArrayList 存放初本身和i的公约数 public static ArrayList maxDivisor(int n ){ ArrayList arrayList = new ArrayList<>(); // 这里使用Math.sqrt是为了防止超时 for (int i = 2; i <= Math.sqrt(n); i++) { if(n % i == 0) { arrayList.add(i); // 当n/i!=i时,需要添加到arraylist中,否则会漏解 if (n / i != i) { arrayList.add(n / i); } } } return arrayList; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] dp = new int[m+1]; // 将dp数组初始化为-1 Arrays.fill(dp,-1); // dp[n]的初始状态为0 dp[n] = 0; for(int i = n; i < m; i++){ // 如果dp[i]=-1 表示当前的位置到不了,所以就不需要往下走了 if(dp[i] == -1) continue; ArrayList arrayList = maxDivisor(i); // 遍历所有的因子 for(int j : arrayList){ // i+j<=m 防止数组越界 // 因为初始化是-1 求最小值min 就需要判断 if(i + j <= m && dp[i+j] != -1){ dp[i+j] = Math.min(dp[i]+1,dp[i+j]); }else if(i + j <= m){ dp[i+j] = dp[i] + 1; } } } //遍历结束就返回dp[m] // 如果里面是-1就表示到达不了 System.out.println(dp[m]); } }

第三题: 不同路径 【LeetCode|Dynamic Programming --- 动态规划刷题(一)】LeetCode 62: 不同路径
描述:
一个机器人位于一个 m x n 网格的左上角(起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

文章图片

解题思路:

状态 F(i,j) : 表示到达(i,j)下标可以走的路径

状态转移方程:
① i == 0 || j == 0, F(i,j) == 1
② F(i,j) = F(i-1,j) + F(i,j-1)

初始状态: F(0,0) = 1;

返回结果: F(m-1,n-1)

代码实现:

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = 1; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(j==0 || i==0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; } }

第四题: 最大子数组和 LeetCode 53: 最大子数组和
描述:
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

文章图片

解题思路:

状态F(i): 表示第i个和最大的值

状态转移方程: F(i) = max(F(i),F(i-1)+F(i))

初始状态：F[0] = nums[0];

返回值: 返回max(F(i));

代码实现:

class Solution { public int maxSubArray(int[] nums) { // 状态F(i): 表示第i个和最大的值 // 状态转移方程: F(i) = max(F(i),F(i-1)+F(i)) // 初始状态：F[0] = nums[0]; // 返回值: 返回max(F(i)); int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = dp[0]; for(int i = 1; i < nums.length; i++){ dp[i] = Math.max(nums[i],dp[i-1] + nums[i]); max = Math.max(dp[i],max); } return max; } }

第五题: 最小路径和 LeetCode 64: 最小路径和
描述:
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

文章图片

解题思路:

状态F(i,j):　到达i,j的最小路径和

状态转移方程: F(i,j) = min(F(i,j-1),F(i-1,j))+F(i,j)
i == 0 => F(i,j) = F(i,j-1) + F(i,j)
j == 0 => F(i,j) = F(i-1,j) + F(i,j)

初始状态: F(0,0) = gird[0][0]

返回值: F(grid.length-1,grid[0].length-1)的值就是返回值

代码实现:

class Solution { public int minPathSum(int[][] grid) { // 状态F(i,j):　到达i,j的最小路径和 // 状态转移方程: F(i,j) = min(F(i,j-1),F(i-1,j))+F(i,j) //i == 0 => F(i,j) = F(i,j-1) + F(i,j) //j == 0 => F(i,j) = F(i-1,j) + F(i,j) // 初始状态: F(0,0) = gird[0][0] // 返回值: F(grid.length-1,grid[0].length-1)的值就是返回值 for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[i].length; j++){ if(i == 0 && j == 0) continue; if(i == 0) grid[i][j] = grid[i][j-1]+grid[i][j]; else if(j == 0) grid[i][j] = grid[i-1][j]+grid[i][j]; else grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j]; } } return grid[grid.length-1][grid[0].length-1]; } }