算法问题——动态规划算法理解

动态规划的就是的将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次 ，最终获得原问题的答案。

动态规划是一种自下而上的一种的思考：就是这个问题是由于前一个问题+加上当前的问题的而得到的结果。F(i)=x+F(i-x)这样的一种的表达。这样的是一种递归的调用，这样的会占用系统的栈空间的，所以在很多时候是最好不采用这样的一种方式。而记忆化搜索是一种的自上而下的一种的方法来实现的。F(i)+x=F(i+x)的这样的一种表现形式。用小数据问题解决大数据问题。采用的是的数组来记录好当前的转态的一种的。

70. 爬楼梯

    /**
     * 递归函数
     *
     * @param n
     * @return
     */
    public int test(int n) {
        return calway(n);
    }

    private int calway(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return calway(n - 1) + calway(n - 2);
    }

 /**
     * 记忆化递归的思想
     *
     * @param n
     * @return
     */
    public int solution(int n) {
        //这个是记忆的数组 记录是的每一个台阶的方法
        int[] memeo = new int[n + 1];
        return climbstairs1(n, memeo);
    }

    private int climbstairs1(int n, int[] memeo) {
        if (memeo[n] > 0) {
            return memeo[n];
        }
        if (n == 1 || n == 2) {
            memeo[n] = n;
        } else {
            memeo[n] = climbstairs1(n - 1, memeo) + climbstairs1(n - 2, memeo);
        }
        return memeo[n];
    }

120. 三角形最小路径和

状态的转移方程：dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+tragle[i][j]

边界的dp[i][0]=dp[i-1][0]+trangle[i][0]

边界的dp[i][j]=dp[i-1][i-1]=trangle[i][i]

/**
 * Copyright (C), 2018-2020
 * FileName: 最小路径和64
 * Author:   xjl
 * Date:     2020/9/7 12:27
 * Description:
 */
package 动态规划问题集合;

import org.junit.Test;

/**
 * 写出这个转态的转移方程式
 * dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+dp[i][j]
 */
public class 最小路径和64 {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid == null || m == 0 || n == 0) {
            return 0;
        }
        //1 设置一个数组
        int[][] dp = new int[m][n];

        //3 确定的边界的时候
        dp[0][0] = grid[0][0];
        //当列为0的时候的边界
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //当行为0的时候的边界
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        //2 状态转移方程
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        //结果是最后的
        return dp[m - 1][n - 1];
    }

    @Test
    public void test() {
        int[][] array = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int i = minPathSum(array);
        System.out.println(i);
    }
}

120. 三角形最大路径和||

64. 最小路径和

/**
 * Copyright (C), 2018-2020
 * FileName: 最小路径和64
 * Author:   xjl
 * Date:     2020/9/7 12:27
 * Description:
 */
package 动态规划问题集合;

/**
 * 写出这个转态的转移方程式 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+dp[i][j]
 */
public class 最小路径和64 {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid == null || m == 0 || n == 0) {
            return 0;
        }
        //1 设置一个数组
        int[][] dp = new int[m][n];

        //3 确定的边界的时候
        dp[0][0] = grid[0][0];
        //当列为0的时候的边界
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //当行为0的时候的边界
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        //2 状态转移方程
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        //结果是最后的
        return dp[m - 1][n - 1];
    }
}

343. 整数拆分

/**
 * Copyright (C), 2018-2020
 * FileName: 整数拆分343
 * Author:   xjl
 * Date:     2020/9/7 14:04
 * Description:
 */
package 动态规划问题集合;

public class 整数拆分343 {
    /**
     * 分割两个部分 这是一个递归问题 时间hi超过限制  可能需要采用的记忆化递归的算法
     *
     * @param n
     * @return
     */
    static int[] array;

    public static int integerBreak(int n) {
        array = new int[n + 1];
        return test(n);
    }

    /**
     * 这个超过时间限制 也是使用了记忆化搜索的
     *
     * @param n
     * @return
     */
    public static int test(int n) {
        if (n == 1) {
            return 1;
        }
        if (array[n] != 0) {
            return array[n];
        }
        int res = -1;
        //能分割多少的中的方法嗯？
        for (int i = 1; i 2)k (k>2) 间房屋，有两个选项：
 
    偷窃第 kkk 间房屋，那么就不能偷窃第 k−1k-1k−1 间房屋，偷窃总金额为前 k−2k-2k−2 间房屋的最高总金额与第 kkk 间房屋的金额之和。
 
    不偷窃第 kkk 间房屋，偷窃总金额为前 k−1k-1k−1 间房屋的最高总金额。
 
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 kkk 间房屋能偷窃到的最高总金额。
 
用 dp[i]dp[i]dp[i] 表示前 iii 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
 
 
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}
 
/**
 * Copyright (C), 2018-2020
 * FileName: 打劫1
 * Author:   xjl
 * Date:     2020/9/8 15:58
 * Description:
 */
package 动态规划问题集合;

import java.util.Arrays;

public class 打劫1 {
    public static int rob(int[] nums) {
        return testrob(nums, 0);
    }

    /**
     * 考虑的是的nums[index…… nums.size（）]这个范围的所有的房子
     *
     * @param nums
     * @param index
     * @return
     */
    public static int testrob(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }
        //开始抢劫这个房子以后的所有房子
        int res = 0;
        for (int i = index; i < nums.length; i++) {
            res = Math.max(res, nums[i] + testrob(nums, index + 2));
        }
        return res;
    }

    /**
     * 采用的是记忆化搜索的方法来实现
     * @param nums
     * @param index
     * @return
     */
    static int[] memo;

    public static int rob1(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return testrob2(nums, 0);
    }

    public static int testrob2(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }
        //判断时候有值 如果有值就不需要计算了  如果是没有就需要的是的计算
        if (memo[index] != -1) {
            return memo[index];
        }
        //开始抢劫这个房子以后的所有房子
        int res = 0;
        for (int i = index; i < nums.length; i++) {
            res = Math.max(res, nums[i] + testrob2(nums, i + 2));
        }
        //每一次将这个保留这个转态
        memo[index] = res;
        return res;
    }
}
 
public int rob4(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题：
        // f(k) = 偷 [0..k) 房间中的最大金额
        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
        int N = nums.length;
        //表示的是的最大的数字
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int k = 2; k