“面向目标值的排列匹配“和“面向目标值的背包组合问题“的区别和leetcode例题详解

1 目标值排列匹配

1.1 从目标字符串的角度来看，LC139是一个排列问题，因为最终目标子串的各个字符的顺序是固定的？

当我们从目标字符串 s 的角度来看 LC139 “单词拆分” 问题，确实可以认为它涉及到排列的概念，但这种排列是在一个更宏观的层面上，而不是在我们通常讨论组合和排列问题时所指的那种[参考1.4]。
在这里插入图片描述

1.1.1 排列的角度

在 “单词拆分” 问题中，目标字符串 s 的字符顺序是固定的。我们不能改变这些字符的顺序。我们的任务是确定是否可以通过字典中的单词（这些单词的内部字符顺序也是固定的）来构造出这个特定顺序的字符串。从这个角度看，确实涉及到了字符的“排列”——但这是指字符串 s 和字典中单词的内部字符顺序，而不是字典中单词作为整体的排列顺序。

1.1.2 组合的角度

然而，当我们讨论解决这个问题的算法时，我们通常将其视为一个组合问题。这是因为我们关心的是如何从字典中选择单词（并且可以重复选择）来构造字符串 s，而不是这些单词的选择顺序。我们可以以任何顺序检查和组合这些单词，只要它们最终能组合成目标字符串 s。

1.1.3 动态规划的应用

在动态规划的应用中，我们通常关注的是如何逐步构建目标字符串，并在每一步检查是否可以使用字典中的单词来形成当前长度的子串。这种方法更侧重于组合（即哪些单词被选中来构造子串）而不是单词的选择顺序。

1.1.4 总结

因此，虽然从目标字符串 s 的角度来看，LC139 “单词拆分” 涉及到字符的排列，但在解决问题的算法层面，它更像是一个组合问题。这是因为我们关注的是如何从字典中选择单词来构造字符串 s，而不是这些单词的选择顺序。

1.3 例题一：爬楼梯

在这里插入图片描述

1.2.1 解析

这是一个面向目标值的排列问题，假如现在有一个三层楼梯，小明到达的方案有三种，如上图示例二所示，其中小明"先跳两级再跳一级"和"先跳一级再跳两级"是两种不同的方案（如果放到组合中这就是同一种组合），那么这就是一种面向目标值的排列问题，

1.2.2 答案

	// 泛化问题的答案，这里的j=2可以调整为j=k，表明"可以跳1到k级中的任意一级的楼梯"
    public int climbStairs(int n) {
        
        int[]f=new int[n+1];
        f[0]=1;
        f[1]=1;
        for(int i=2;i<=n;i++){
            int s=0;
            for(int j=1;j<=2;j++){
                s+=f[i-j];
            }
            f[i]=s;
        }
        return f[n];
    }

1.3 爬楼梯改编题

在这里插入图片描述

1.3.1 为什么这是一个“面向目标值的排列匹配”问题？

答：因为不同的排列方案，其代价不同，所以必然是一个排列问题，比如"从0到1花费10，从1跳2阶梯到3花费15"，这种排列花费25，但是"从0到2花费20，从2跳1阶梯到3花费10",这种排列花费30.

1.3.2 答案

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        if(n<2){
            return 0;
        }
        int[]f=new int[n+1];

        for(int i=2;i<=n;i++){
            f[i]=Math.min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
        }

        return f[n];
    }
}

1.4 例题：Leetcode139. 单词拆分

在这里插入图片描述

1.4.1 这为什么是一个面向目标值的排列匹配问题？

以图中的例一为例，从单词列表中凑成leetcode本身要求leet在code之前，而不是满足任意顺序凑成就行，那么必然就是一个排列问题

1.4.2 答案

    public boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        char[]cs=s.toCharArray();
        int m=wordDict.size();

        HashSet<String>set=new HashSet<>(wordDict);
        boolean[]f=new boolean[n+1];
        f[0]=true;

        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(f[j]&&set.contains(s.substring(j,i))){
                    f[i]=true;
                    break;
                }
            }
        }
        return f[n];
    }

1.5 关于LC单词拆分的其他变体问题

Leetcode139单词拆分及其多种变体问题

2 背包组合问题

基本上背包问题无论从目标值角度还是元素列表角度都是组合问题，因为背包只涉及到数量关系的满足，如果两个排列的数量关系相同，那么他们对问题的贡献值是一样的，可以视为一个同组合

2.1 以《lc 416. 分割等和子集》为例，可以发现背包问题只关注凑成的数量正确，对于排列的方式不关心，所以是一个组合问题

在这里插入图片描述

    public boolean canPartition(int[] nums) {
        int n=nums.length;
        int s=0;
        for(int i=0;i<n;i++){
            s+=nums[i];
        }
        if(s%2==1){
            return false;
        }
        boolean[]f=new boolean[s/2+1];
        f[0]=true;
        for(int i=0;i<n;i++){
            for(int j=s/2;j>=nums[i];j--){
                f[j]=f[j]||f[j-nums[i]];
            }
        }
        return f[s/2];

    }