Python|动态规划与回溯求数字个数

简介: Python|动态规划与回溯求数字个数

问题描述

给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n

示例:

输入: 2

输出: 91

解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。


动态规划思考及解决

读完该问题,会想到动态规划+排列组合来决解,因为是求的不同数字的个数,所以要将每一个满足的值加起来,故采用动态规划是很方便的。

第一步:创建一个dp数组,记录下n=0-2的个数(dp=[1,10,91])

第二步:判断n>=3,满足进行遍历3-n,利用排列组合计算出不同的数字个数;

第三步:将满足的个数加上前一个的个数并放入dp数组中,最后返回dp数组的最后一个值。

代码:

#动态规划

class Solution:

    def countNumbersWithUniqueDigits(self, n: int) -> int:

        dp=[1,10,91]

        if n>=3:

            for i in range(3,n+1):

                s,k,g=9,9,0  #s为排列组合所求i值不同数字的个数

                while g<i-1:

                    s=s*k

                    k-=1

                    g+=1

                dp.append(s+dp[-1])

            return dp[-1]

        else:

            return dp[n]


回溯思考及解决

当然该题也能用递归来进行解答,回溯算法则更加的简洁,不需要设很多的未知数。

第一步:创建一个递归函数,将一个空字符串res与字符串l=’1234567890’传入该函数中;在构造函数中创建一个self.num=0来记录个数;

第二步:遍历字符串l,并进行函数递归操作,将取到的字符从l中取出;

第三步:设置递归终止条件,且执行一次递归self.num+=1,最终返回self.num

代码:

#递归解决:

class Solution:

    def __init__(self):

        self.num=0

    def countNumbersWithUniqueDigits(self, n: int) -> int:

        def A(res,l):

            if res:

                if int(res)>=10**n:#终止条件

                    return

                if res[0]==str(0):#第一位不能为0

                    return

            self.num+=1

            for i in l:

                A(res+i,l.replace(i,''))

        A('','1234567890')

        return self.num


参考文献

本文主要是讲了从动态规划+排列组合来解答该题,和回溯算法解答该题的思路以及代码,当然两种方法都可,虽然回溯算法易理解且简洁,但算法时间复杂度过高。

目录
相关文章
|
4月前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
72 8
|
4月前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
67 3
|
17天前
|
存储 算法 Python
【10月更文挑战第16天】「Mac上学Python 27」小学奥数篇13 - 动态规划入门
本篇将通过 Python 和 Cangjie 双语介绍动态规划的基本概念,并解决一个经典问题:斐波那契数列。学生将学习如何使用动态规划优化递归计算,并掌握编程中的重要算法思想。
81 3
|
5月前
|
SQL 算法 数据挖掘
动态规划Dynamic programming详解-编辑距离问题【python】
动态规划Dynamic programming详解-编辑距离问题【python】
|
4月前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
112 2
|
4月前
|
算法 程序员 Python
算法小白到大神的蜕变之路:Python分治法、贪心、动态规划,一步步带你走向算法巅峰!
【7月更文挑战第9天】探索算法之旅,以Python解锁编程高手之路。分治法如二分查找,将复杂问题拆解;贪心算法解决活动选择,每次选取局部最优;动态规划求斐波那契数列,避免重复计算,实现全局最优。每一步学习,都是编程能力的升华,助你应对复杂挑战,迈向算法大师!
46 1
|
4月前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
65 1
|
4月前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
70 1
|
4月前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
47 1
|
4月前
|
算法 索引 Python
逆袭算法界!Python分治法、贪心算法、动态规划深度剖析,带你走出算法迷宫!
【7月更文挑战第8天】分治法,如快速排序,将大问题分解并合并解;贪心算法,选择局部最优解,如活动选择;动态规划,利用最优子结构避免重复计算,如斐波那契数列。Python示例展示这些算法如何解决实际问题,助你精通算法,勇闯迷宫。
45 1