动态规划

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

动态规划的三特点

1. 把原来的问题分解成了几个相似的子问题。
2. 所有的子问题都只需要解决一次。
3. 储存子问题的解。

动态规划的四要素

1. 状态定义
2. 状态间的转移方程定义
3. 状态的初始化
4. 返回结果

第一题 : 零钱兑换

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

解题思路:

1. 状态 F(i) : 表示凑成i所需最少的硬币个数
2. 状态转移方程: F(i) = F(coins[j]) + min(F(i-coins[j]))(coins[j[表示已有的硬币)
3. 初始状态: F(0) = 0; F(coins[j]) = 1 (已有的面值可以直接拿,所以是1)
4. 返回结果: F(M) (M表示amount)

代码实现:

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号石板

解题思路:

1. 状态 F(i) : 表示到达i的最小步数
2. 状态转移方程: F(i+j) = min(F(i)+1,F(i+j)) (i表示所在位置,j表示可以跳的步数)
3. 初始状态: F(N) = 0; (N表示起始位置)
4. 返回结果: F(M) (M表示需要到达的石板)

代码实现:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    // 用ArrayList 存放 初本身和i的公约数
    public static ArrayList<Integer> maxDivisor(int n ){
        ArrayList<Integer> 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<Integer> 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 62: 不同路径
描述:
一个机器人位于一个 m x n 网格的左上角(起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

解题思路:

1. 状态 F(i,j) : 表示到达(i,j)下标可以走的路径
2. 状态转移方程:
   ① i == 0 || j == 0, F(i,j) == 1
   ② F(i,j) = F(i-1,j) + F(i,j-1)
3. 初始状态: F(0,0) = 1;
4. 返回结果: 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 ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

解题思路:

1. 状态F(i): 表示第i个和最大的值
2. 状态转移方程: F(i) = max(F(i),F(i-1)+F(i))
3. 初始状态：F[0] = nums[0];
4. 返回值: 返回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 ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

解题思路:

1. 状态F(i,j):　到达i,j的最小路径和
2. 状态转移方程: 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)
3. 初始状态: F(0,0) = gird[0][0]
4. 返回值: 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];
    }
}