算法训练——剑指offer(动态规划算法)摘要

摘要

一、动态规划原理与解题方法

二、动态规划算法练习题目

2.1 跳台阶问题

package 动态规划算法;

import org.junit.Test;

/**
 * @Classname JZ69跳台阶问题
 * @Description TODO
 * @Date 2022/2/11 18:54
 * @Created by xjl
 */
public class JZ69跳台阶问题 {
    /**
     * @description 
     * 1、题解一分析出本题f(n)可以拆分出重叠子问题f(n-1)、f(n-2);
     * 2、f(n)=f(n-1)+f(n-2)是动态规划的状态转移方程；
     * 3、f(0)=1,f(1)=1是动态规划的初始状态；
     * 4、dp为一维数组，其中dp[i]的值代表青蛙跳第n个台阶的方法数；
      * @param: target
     * @date: 2022/2/12 8:12
     * @return: int
     * @author: xjl
    */
    public int jumpFloor(int target) {
        if (target<=2){
            return target;
        }
        int[] array=new int[target];
        array[0]=1;
        array[1]=2;
        for (int i=2;i<target;i++){
            array[i]=Math.max(array[i],array[i-2]+array[i-1]);
        }
        return array[target-1];
    }


    @Test
    public void test(){
        int i = jumpFloor(7);
        System.out.println(i);
    }
}

2.2 股票问题

2.3 小偷问题

2.4 连续数组最大和问题

package 动态规划算法;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Classname JZ42连续子数组的最大和
 * @Description f(n)=Math.max(f(n-1)+dp(n),dp(n))
 * @Date 2022/2/11 18:56
 * @Created by xjl
 */
public class JZ42连续子数组的最大和 {

    public int FindGreatestSumOfSubArray(int[] array) {
        int[] arr = new int[array.length];
        int max = array[0];
        arr[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            arr[i] = Math.max(array[i] + arr[i - 1], array[i]);
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    public int FindGreatestSumOfSubArray2(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i] = Math.max(array[i] + array[i - 1], array[i]);
            max = Math.max(max, array[i]);
        }
        return max;
    }


}

2.5 礼物最大问题（背包问题）

2.6 最长子串问题

2.7 数字翻译字符串

package 动态规划算法;

/**
 * @Classname JZ46把数字翻译成字符串
 * @Description TODO
 * @Date 2022/2/12 15:39
 * @Created by xjl
 */
public class JZ46把数字翻译成字符串 {

    /**
     * @description 这个的是有效的IP
     * @param: null
     * @date: 2022/2/12 15:39
     * @return:
     * @author: xjl
     */

    public int solve(String nums) {
        if(nums.length() == 0 || nums.charAt(0) == '0'){
            return 0;
        }
        int[] dp = new int[nums.length()];
        dp[0] = 1;
        for(int i = 1; i < dp.length; i++){
            if(nums.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            int num = (nums.charAt(i-1)-'0')*10 + (nums.charAt(i)-'0');
            if(num >= 10 && num <= 26){
                if(i == 1){
                    dp[i] += 1;
                }else{
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[nums.length()-1];
    }
}

2.8 斐波那契数列

package 动态规划算法;

import org.junit.Test;

/**
 * @Classname JZ10斐波那契数列
 * @Description TODO
 * @Date 2022/2/11 18:54
 * @Created by xjl
 */
public class JZ10斐波那契数列 {
    /**
     * @description 动态规划
     * @param: n
     * @date: 2022/2/11 20:44
     * @return: int
     * @author: xjl
     */
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int[] result = new int[n + 1];
        result[0] = 0;
        result[1] = 1;
        for (int i = 2; i < result.length; i++) {
            result[i] = result[i - 2] + result[i - 1];
        }
        return result[n];
    }

    /**
     * @description 递归方式
     * @param: n
     * @date: 2022/2/11 20:45
     * @return: int
     * @author: xjl
     */
    public int Fibonacci2(int n) {
        if (n < 2) {
            return n;
        }
        int res = Fibonacci2(n - 1) + Fibonacci2(n - 2);
        return res;
    }


    @Test
    public void test(){
        int i = Fibonacci2(4);
        System.out.println(i);
    }
}

博文参考

灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频

动态规划入门：从记忆化搜索到递推【基础算法精讲 17】_哔哩哔哩_bilibili