💕"轻舟已过万重山!"💕
作者：Lvzi
文章主要内容：算法系列–算法系列–动态规划–特殊的状态表示–分析重复子问题
大家好,今天为大家带来的是
算法系列--动态规划--特殊的状态表示--分析重复子问题
一.组合总数IV
链接:
https://leetcode.cn/problems/combination-sum-iv/
分析:
本题名字叫做组合问题,但实际上是一个排列问题,需要说明的是背包问题解决的是有限制条件下的"组合"问题,本题是一个排列问题,其实根本就无法使用背包问题的思路解决
那该如何解决呢?而且这道题还不太容易分析状态表示,其实这是动态规划问题中比较难的一种问题,状态表示的确立应该是:在分析问题的时候,发现重复的子问题,并抽象出状态表示
目的是求出总和等于target的所有排列方式,如果固定第一个数为a,那么就是求出总和等于target-a的所有排列方式,这里的重复子问题就是求出总和等于某个数的所有排列方式
状态表示:
dp[i]:总和等于i的所有排列方式
状态转移方程:
还是根据最后一个位置的状态划分问题
nums[j]表示的是数组中任意的一个数,只要符合条件(i >= nums[j]),都可以作为组成总和为i的排列方式的一种,那么只需在前面判断组成和为i-nums[j]的所有排列数即可,即dp[i - nums[j](注意本题是排列,排列!!!是区分顺序的!!!)
再次明确,本题是一个排列问题,是从数组中的所有元素选择出一些排列方式,使总和为target就行,在这个过程中,必须要保证添加的数字不能超过总和
初始化:
dp[0] = 1:凑出总和为0的所有方式–>什么也不选–>空集也算一种情况
算法系列--动态规划--特殊的状态表示--分析重复子问题（下）https://developer.aliyun.com/article/1480869?spm=a2c6h.13148508.setting.17.352e4f0eqTYwhH
