数的划分
题目 : https://www.luogu.com.cn/problem/P1025不理解为什么状态转移方程是(i代表数字, j代表划分的个数, f 代表数字 i 划分成 j 个数字的和一共的方法数if(i >= j) f = f + f;
f 我懂, 就是第一个是 1 , 后面剩下的数分 j-1 个位置
但是我自己算的时候感觉应该是 f+ f + ... + f
这样才对 , 但是又有重复 , 求解为什么是上面的那个方程 , 怎么推的 你是要程序代码还是要运算什么的 编程追风梦 发表于 2022-9-25 17:18
你是要程序代码还是要运算什么的
就是解释这个方程是怎么推出的 本帖最后由 jhq999 于 2022-9-25 18:24 编辑
不懂什么状态转移方程{:5_94:}
这道题我的思路
n m
n-m+1 1 1....1(m-1个1）
n-m-1+1 2 1.....1(m-2 g个1)
n-m-2+1 3 1....1， n-m-2+1 2 2 1.....1
n-m-3 +1 4 1....1 , n-m-3+1 3 2 1......1, n-m-3+1 2 2 2 1....1 //就是后面只能小于等于前面
......
n-m-i+1 j 1..........1(m-j个1）
结束条件:n-m-i+1<j
7 3
5 1 1
4 2 1
3 3 1 3 2 2 柿子饼同学 发表于 2022-9-25 17:32
就是解释这个方程是怎么推出的
好的，我试着解答一下 其实你可以这样去想，用动态规划来思考
什么是动态规划？在递归的时候，我们可以通过不断地分解问题，将复杂的任务简化为最基本的小问题，比如基于递归实现的归并排序，排列，组合等。不过有时候，我们并不用处理所有可能的情况，只要找到满足条件的最优解就可以了，这种情况下，我们需要在各种可能的局部解中，找出那些可能达到最优的局部解，而放弃其他的局部解，这个寻找最优解的过程叫动态规划。怎么判断一个问题是否可以由动态规划来解决？首先，如果一个问题有多种可能，看上去需要排列或者组合的思想，但是最终求的只是最优解，如最大值，最小值，最短子串，最长子串等，可以试试使用动态规划。其实，状态转移方程是个关键。你可以用状态转移表来帮助自己理解整个过程。如果能找到准确的转移方程，那么离最终的代码实现也就不远了 。这里说下什么是状态转移方程：从上一个状态到下一个状态之间可能存在一些变化，以及基于这些变化的最终决策结果。我们把这样的表达式称为状态转移方程。所有的动态规划算法中，状态转移是关键。来个例子假如有 2 块，3 块，7 块面额的纸币，如何使用最小的纸币数量来凑成 100 块。一般会优先想到这样的方法：优先使用大面额的，不够的话再用次大面额的，直到凑成 100 块。100 除以 7 = 14 余数为 2 ，正好再用一张 2 的面额就可以了，也就是说最低 15 张。这属于贪心算法，今天先不讲。动态规划的解题思路：c(n) 表示凑成 n 元的最小纸币数量c(100) = c(93 +7） = c(93）+1c(100) = c(97 +3） = c(97）+1c(100) = c(98 + 2） = c(98）+1如果分析到这里，你可能会想到递归是一种解决思路，没错，但递归从大到小的分解其实保留了每一步的结果，并没有舍弃非最优解，效率并不高。接下来就是找 c(93），c(97）， c(98）哪个值最小，按照同样的方法，继续进行分解，直到 c(2) = 1，c(3) =1, c(4) = 2, c(5) = 2, c(6)=2, c(7)=1, c(8) = 3。这里可以推出状态转移方程：其中，c 表示总额为 i 的时候，所需要的最少钱币数，其中 j=1,2,3,…,n，表示 n 种面额的钱币，value 表示第 j 种钱币的面额。c 表示选择第 j 种钱币的时候，上一步为止最少的钱币数。需要注意的是，i - value(j) 需要大于等于 0，而且 c = 0。
然后，从小到大，我们可以先在草纸上演算下，并验证状态转移方程
接下来的事情就是将这种有规律的过程转化为源代码了，到这里其实已经没有难度了。#encoding = utf-8
def count_dp(num):
kinds =
##循环使用tmp，降低内存占用
tmp =
result = [,,,,,,]
if num <2:
return
elif 2 <= num <=8:
return tmp,result
else:
for i in range(9,num+1):
values=[] #保留三个数据，取最小的那个
for kind in kinds:
values.append( (tmp[(i-2-kind)%7] + 1, (i-2-kind)%7 , kind) )
min_value = min(values) ##默认按第一个值比较，取最小的
#print(min_value)
tmp_result = result].copy()
#print(tmp_result)
tmp_result.append(min_value)
#print(tmp_result)
##循环保存在临时数组中
tmp[(i-2)%7] = min_value
result[(i-2)%7].clear()
result[(i-2)%7] = tmp_result.copy()
return tmp[(num-2)%7],result[(num-2)%7]
def count_recursion(num):
kinds =
##循环使用tmp，降低内存占用
tmp =
if num <2:
return
elif 2 <= num <=8:
return tmp
else:
##采用递归方式
values=[] #保留三个数据，取最小的那个
for kind in kinds:
values.append(count_recursion(num - kind))
min_value = min(values)+1 ##默认按第一个值比较，取最小的
return min_value
if __name__ == "__main__":
for i in :
print(i,'->',count_dp(i))
for i in :
print(i,'->',count_recursion(i))由于递归的方式特别慢，所以只让它运行到 20 。运行结果如下：1 -> None
2 -> (1, )
3 -> (1, )
4 -> (2, )
5 -> (2, )
6 -> (2, )
7 -> (1, )
8 -> (3, )
9 -> (2, )
10 -> (2, )
100 -> (15, )
1 -> None
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 1
8 -> 3
9 -> 2
15 -> 4
20 -> 4
注：本文转载自 https://cloud.tencent.com/developer/article/1758788主题：动态规划-如何推导出状态转移方程
页:
[1]