动态规划-回溯法-分治网站首页 技术交流

动态规划-回溯法-分治

恶熊比比 2023-05-19 08:00:03

简介动态规划-回溯法-分治

动态规划

动态规划概念

某个问题有很多子问题，每一个子问题都是通过上一个子问题推导出来的

解题步骤

确定dp数组以及数组下标的含义
确定好递推公式
dp数组的初始化
确定好遍历顺序
举例推导dp数组

1. 斐波那契

https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
递归写法：

public static int fib(int n) {
        if(n<=1){
            return n;
        }
        return fib(n-1)+fib(n-2);
    }

dp:

class Solution {
    public int fib(int n) {
        if(n<=1){
            return n;
        }
        //1.dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        int[] dp = new int[n+1];
        //3.dp数组如何初始化
        dp[0]=0;
        dp[1]=1;
	//4. 确定遍历顺序
//从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
        for(int i=2;i<=n;i++){
        //2。 确定好递推公式 
            dp[i]=dp[i-1]+dp[i-2];
        }
        
        return dp[n];
    }
}

2. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/

确定dp数组以及数组下标的含义
每个下标对应当前楼层爬上去的方式有几种
确定好递推公式
当前楼层的方法=当前楼层下两层的方法+当前楼层下一层的方法
//因为你如果是当前要上三阶：可以从1阶跨两步上去，也可以从2阶跨两步上去；
dp数组的初始化
确定好遍历顺序
举例推导dp数组

class Solution {
    public int climbStairs(int n) {
        if(n<=1){
            return n;
        }

        int[] res= new int[n+1];
        res[0]=0;
        res[1]=1;
        res[2]=2;

        for(int i=3;i<=n;i++){
            res[i]=res[i-1]+res[i-2];
        }

        return res[n];
    }
}

3.使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        

        int[] mincost = new int[cost.length];
        mincost[0]=cost[0];
        mincost[1]=cost[1];
        for(int i=2;i<=cost.length-1;i++){
            mincost[i]=Math.min(mincost[i-1],mincost[i-2])+cost[i];
        }

        return Math.min(mincost[cost.length - 1], mincost[cost.length - 2]);
    }
}

回溯法

回溯法用于解决组合优化问题和搜索问题。回溯法的基本思路是通过不断地尝试各种可能的情况来寻找问题的解。在每一步尝试时，如果发现当前方案不能满足要求，就返回上一步并尝试其他可能的方案，直到找到问题的解或者所有可能的方案都已经尝试过。

实现方式是递归

回溯法通常采用递归的方式来实现，每次递归调用时，都会尝试一种可能的情况，并继续递归调用下一步的情况。如果当前方案不能满足要求，则回溯到上一步，尝试其他可能的方案。

回溯法中回到上一步的关键

溯法中的 return 语句是回到上一步的关键。在回溯法中，当搜索到某个状态时，需要尝试所有可能的决策，直到找到解决方案或者确定该状态无法找到解决方案。如果在某个决策点无法找到解决方案，回溯法会回到上一个决策点，并尝试其他的决策方案，直到找到解决方案或者所有决策方案都已经尝试过。

1. 括号生成

https://leetcode.cn/problems/generate-parentheses/

/**
 * 生成有效括号组合的函数
 * @param n 代表生成括号的对数
 * @return 包含所有有效括号组合的列表
 */
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    generate(result, "", 0, 0, n);
    return result;
}

/**
 * 递归函数，用于生成所有可能的括号组合
 * @param result 存储所有有效括号组合的列表
 * @param current 当前已生成的括号组合
 * @param open 当前已添加的左括号数量
 * @param close 当前已添加的右括号数量
 * @param n 代表生成括号的对数
 */
private void generate(List<String> result, String current, int open, int close, int n) {
    // 当生成的字符串长度达到 n*2 时，即为一种有效的括号组合，将其添加到结果列表中
    if (current.length() == n * 2) {
        result.add(current);
        return;
    }
    // 如果还可以添加左括号，则添加左括号并递归调用 generate() 方法
    if (open < n) {
        generate(result, current + "(", open + 1, close, n);
    }
    // 如果已添加的左括号数量大于已添加的右括号数量，则添加右括号并递归调用 generate() 方法
    if (close < open) {
        generate(result, current + ")", open, close + 1, n);
    }
}

2.组合总数

https://leetcode.cn/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    //回溯
    List<List<Integer>> res = new ArrayList<>(); // 用于存储最终结果
    List<Integer> cur = new ArrayList<>(); // 用于存储当前组合
    Arrays.sort(candidates); // 对数组进行排序
    back(candidates, target, 0, cur, res); // 调用回溯算法
    return res; // 返回最终结果
}

public void back(int[] candidates, int target, int start, List<Integer> cur, List<List<Integer>> res) {
    if (target == 0) { // 如果目标值为0，说明找到了一组符合要求的组合，加入最终结果中
        res.add(new ArrayList<>(cur));
        return;
    }
    if (target < 0) { // 如果目标值小于0，说明当前组合不符合要求，直接返回
        return;
    }

    for (int i = start; i < candidates.length; i++) { // 从当前位置开始向后遍历
        if (i > start && candidates[i] == candidates[i - 1]) { // 如果当前数字和上一个数字相同，则跳过该数字，避免生成重复的组合
            continue;
        }
        cur.add(candidates[i]); // 将当前数字加入当前组合
        back(candidates, target - candidates[i], i, cur, res); // 递归调用回溯算法，继续生成组合
        cur.remove(cur.size() - 1); // 回溯，撤销当前数字的选择
    }
}

3. 全排列

https://leetcode.cn/problems/permutations/

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(); // 存储所有排列的列表
        List<Integer> cor = new ArrayList<>(); // 当前排列的列表
        int[] visited = new int[nums.length]; // 标记数组，用于标记数字是否已在当前排列中出现过
        quan(nums, res, cor, visited);
        return res;
    }
    
    public void quan(int[] nums, List<List<Integer>> res, List<Integer> cor, int[] visited) {
        if (cor.size() == nums.length) { // 当前排列已经包含所有数字，将其加入结果列表中
            res.add(new ArrayList<>(cor));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1) { // 如果数字已在当前排列中出现过，则跳过
                continue;
            }
            visited[i] = 1; // 标记数字已在当前排列中出现过
            cor.add(nums[i]); // 将数字添加到当前排列中
            quan(nums, res, cor, visited); // 递归调用 quan 函数，生成下一个数字的排列
            visited[i] = 0; // 恢复标记状态，进行回溯
            cor.remove(cor.size() - 1); // 将数字从当前排列中移除，进行回溯
        }
    }
}

分治法

分治法是一种解决问题的思想，它将一个大问题分成多个相同或相似的子问题，并递归地求解每个子问题，最后将各个子问题的解合并起来，得到原问题的解。

分治法的三个步骤：

分解问题：将原问题分成多个相同或相似的子问题。

解决问题：递归地解决每个子问题。如果子问题足够小，则直接求解。

合并问题：将所有子问题的解合并成原问题的解。

常见的使用分治法解决的问题包括排序问题（如归并排序、快速排序）、查找问题（如二分查找）和计算问题（如矩阵乘法）。

1. 合并K个有序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //判断是否是空链表
        if(lists==null||lists.length==0){
            return null;
        }
        return mergeLists(lists,0,lists.length-1);
    }
    // 递归方法，用于合并链表
    private ListNode mergeLists(ListNode[] lists,int left,int right){
        // 如果左右指针相等，则返回当前链表
        if(left==right){
            return lists[left];
        }
        // 如果左右指针相差1，则合并左右两个链表
        if(left+1==right){
            return megerTwoLists(lists[left],lists[right]);
        }
        // 计算左右指针的中间位置
        int mid = left+(right-left)/2;
         // 分别递归合并左半部分和右半部分的链表
        ListNode leftList = mergeLists(lists,left,mid);
        ListNode rightList = mergeLists(lists,mid+1,right);
        return megerTwoLists(leftList,rightList);

    }
    // 合并两个有序链表
    private ListNode megerTwoLists(ListNode left,ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode p=dummy;
        while(left!=null&&right!=null){
            if(left.val<=right.val){
                p.next=left;
                left=left.next;
            }else{
                p.next=right;
                right=right.next;
            }

            p=p.next;
        }
        p.next=(left!=null)?left:right;
        return dummy.next;
    }
}