16.动态规划和回溯到底什么关系

目标和(LeetCode 494 难度:中等)

16.动态规划和回溯到底什么关系

下面用目标和来对比动态规划和回溯

回溯思路

任何框架的核心思想都是穷举,回溯算法是一个暴力穷举,前面写过算法框架:

	result = []  
	def backtrack(路径, 选择列表):  
	 if 满足结束条件:  
		 result.add(路径)  
		 return  

	 for 选择 in 选择列表:  
	 做选择  
	 backtrack(路径, 选择列表)  
	 撤销选择

关键搞清楚什么是选择,而对于这道题,选择不是明摆着呢嘛?对于一个数字num[i],可以 选择给一个 正号 + 号 或者 一个负号 -号,然后利用回溯穷举:

class Solution {  
        int res=0;  
        int rest=0;  
    public int findTargetSumWays(int[] nums, int target) {  
        helper(nums,0,target);  
        return res;  
    }  
    private void helper(int[] nums,int i, int target){  
        if(i==nums.length){  
            if(rest==target){  
                res++;  
            }  
            return ;  
        }  
        //给个正常符号  
 		rest=rest+nums[i];  
        helper(nums,i+1,target);  
        //回溯  
		 rest=rest-nums[i];  
        //给个 正常符号的相反符号  
 		rest=rest+-nums[i];  
        helper(nums,i+1,target);  
        //回溯  
 		rest=rest+nums[i];  
    }  
}

消除重叠子问题

动态规划比回溯算法快,因为动态规划 消除了重叠子问题

如何发现重叠子问题呢?看看是否出现过重复的状态。对于递归来说,函数参数中会变的参数就是状态,对于 helper()来说,会变的参数是 itarget

先抽象递归过程

void backtrack(int i,int rest){
	backtrack(i+1,rest-nums[i]);
	backtrack(i+1,rest+nums[i]);
}

举个简单的例子 ,如果nums[i]==0,会发生什么?

void backtrack(int i,int rest){
	backtrack(i+1,rest);
	backtrack(i+1,rest);
}

你看这样就出现了两个状态完全相同的递归函数,无疑这样样的递归计算就是重复的。这就是重叠子问题,而且,只要我们能够找到一个重叠子问题,那一定还存在很多的重叠子问题

因此,状态(i,rest)是可以用备忘录技巧去优化的:

 int findTargetSumWays(int nums[],int target){
	if(nums.length==0)return 0;
	return dp(nums,0,target);_ 
 }
 //备忘录
 HashMap<String,Integer>  memo=new HashMap<>();  
int dp(int nums[],int i,int rest){  
    //base case  
 if(i==nums.length){  
        if(rest==0){  
            return 1;  
        }  
        return 0;  
    }  
    //把他们转成字符串才能作为哈希表的键  
 	String key=i+","+rest;  
    if(memo.containsKey(key)){  
        return memo.get(key);  
    }  
    //还是穷举  
 	int result=dp(nums,i+1,rest-nums[i])+dp(nums,i+1,rest+nums[i]);  
    memo.put(key,result);  
    return result;  
}

可以把状态转化为字符串作为哈希表的键,这是一个常用的技巧。

动态规划

其实这个问题可以转为一个子集切分问题,而子集切分问题又是一个背包问题。动态规划就是让人捉摸不透。

首先,如果把nums切分成两个子集A和B,分别代表分配+号 和分配** - 号 的数字,那么他们的目标和target**的存在关系:

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A)+sum(A) = target + sum(B) + sum(A)
2*sum(A) = target + sum(nums)

综上所述,可以推出sum(A) = (target + sum(nums))/2,也就是把原问题转化成:nums中存在几个子集A,使得A中元素和为((target + sum(nums))/2)。

子集切分问题在经典动态规划:子集背包问题讲过,现在实现一个函数:

 //计算nums中有几个子集的和为 sum
 int subsets(int nums[],int sum){}

然后这样调用函数:

int findTargetSumWays(int nums,int target){
	int sum=0;
	for(int n:nums)sum+=n;
	//这两种情况,不可能存在合法的子集划分
	if(sum<target||(sum+target)%2==1){
		return 0;
	}
	return subsets(nums,(sum+target)/2)
}

好的,变成背包问题的标准形式:

有一个背包,容量为sum,现在给你N个物品,第 i 个物品的重量为 nums[i-1](1<= i <= N),每个物品只有一个,请问有几种不同的方法,能恰好装满这个背包?

现在,这就是一个正宗的动态规划了。

第一步明确两点,状态选择

对于背包问题,这个都是一样的,状态就是 “背包的容量” “可选择的物品” ,选择就是 装不装

第二步,明确dp数组的定义

按照背包的套路,可以给出以下定义:

**dp[i][j]=x **表示,若只在前i个物品 中选择,且当前背包容量为j,则最多都有X种方法 可以使得背包恰好装满。

翻译成我们现在的问题,若只在nums的前 i 个 元素中选择,目标和为 j ,最多有x中划分的方法

根据这个定义,显然,dp[0][...]=0,因为没有物品的话,根本没办法装进背包;dp[...][0]=1,如果背包最大承载量为0, “ 什么都不装 ” 就是唯一的一种装法。

我们要求的答案就是:dp[N][sum],即使用N个物品,有多少种方法可以装满容量为sum的背包?

第三步,根据选择,思考状态转移的逻辑

  • 如果不把nums[i]装入子集,或者说不把第 i 个物品装入背包,那么,恰好装满背包的方法就取决于上一次的状态dp[i-1][j],继承之前的结果
  • 如果把nums[i]装入子集,或者说把第 i 个物品装入背包,那么要看前** i-1** 个物品有几种方法可以装满 j-nums[i-1]的重量就行了,所以就取决于dp[i-1] [j-nums[i-1]];

注意:这里说的 i 是从 1 开始算的,而数组nums的索引是从0开始的,nums[i-1]代表第 i 个物品的重量,j-nums[i-1]就是背包装入物品 i 之后 还剩下的 容量

由于dp[i][j]为装满背包的总方法数,所以应该对以上两种方法求和,得到状态转移方程。

dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];

然后根据状态转移方程推出动态规划算法:

int subsets(int nums[],int sum){  
    int n=nums.length;  
    int[][] dp=new int[n+1][sum+1];  
    //base case  
 	for (int i = 0; i <=n; i++) {  
        dp[i][0]=1;  
    }  
    for (int i = 1; i <=n ; i++) {  
        for (int j = 0; j <=sum; j++) {  
            if(j-nums[i-1]<0){  
                //背包容量不足,继承之前的结果  
 				dp[i][j]=dp[i-1][j];  
            }else {  
                dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];  
            }  
        }  
    }  
    return dp[n][sum];
上一篇:Django REST framework框架( RESTful设计方法)


下一篇:luogu P3919 [模板]可持久化数组(可持久化线段树/平衡树)(主席树)