蓝桥杯-平方拆分
没有白走的路，每一步都算数🎈🎈🎈
题目描述：
将2019拆分成两两不相同的若干个完全平方数之和，一共有多少种不同的方法
注意交换顺序视为同一种方法，例如
\begin{equation} 13^{2}+25^{2}+35^{2} = 2019 \end{equation}
与
\begin{equation} 13^{2}+35^{2}+25^{2} = 2019 \end{equation}
视为同一种方法
输入描述：
输入数据即为2019，本题是一道填空题
输出描述：
输出最后的所有满足平方和相加之后的结果等于2019的无重复组合的组合数
算法暴力for:
关键点是要写很多重的for循环，以下代码是部分for循环的代码
##for i in range(50):
## for j in range(i+1,50):
## if a[i]**2+a[j]**2 == 2019:
## print(a[i],a[j])
## cnt+=1
##
##for i in range(50):
## for j in range(i+1,50):
## for k in range(j+1,50):
## if a[i]**2+a[j]**2+a[k]**2 == 2019:
## print(a[i],a[j],a[k])
## cnt+=1
##
##for i in range(50):
## for j in range(i+1,50):
## for k in range(j+1,50):
## for l in range(k+1,50):
## if a[i]**2+a[j]**2+a[k]**2+a[l]**2 == 2019:
## cnt+=1
##for i in range(50):
## for j in range(i+1,50):
## for k in range(j+1,50):
## for l in range(k+1,50):
## for m in range(l+1,50):
## if a[i]**2+a[j]**2+a[k]**2+a[l]**2+a[m]**2 == 2019:
## cnt+=1dfs算法：
import os
import sys
a = [int(i)*int(i)for i in range(1,52)]
a = [0]+a
cnt = 0
def dfs(x,i):
global cnt
if x>2019:
return
if x == 2019:
cnt+=1
return
for j in range(i+1,51):
dfs(x+a[j],j)
## return 1
dfs(0,0)
print(cnt)for循环中下标的遍历，从哪个位置开始遍历，很关键
线性dp:
import os
import sys
num = [int(i)*int(i)for i in range(1,50)]
n = len(num)
print(n)
dp = [[0]*2020 for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
for j in range(2020):
dp[i][j] = dp[i-1][j]
if j>=num[i-1]:
dp[i][j]+=dp[i-1][j-num[i-1]]
print(dp[-1][-1])- 找到最开始的值
- 找到状态转移方程
每日一句
摘自《平凡的世界》：
人之所以痛苦，在于追求错误的东西。如果你不给自己烦恼，别人也永远不可能给你烦恼。因为你自己的内心，你放不下。好好的管教你自己，不要管别人。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
