python-2^k进制数

解题思路:

动态规划

建立一个大小为（m+1）*（maxnum）的二维数组dp。其中m代表r最多能划分的位数，maxnum代表r中每一位的最大值。

dp[i][j]代表r有i位，最高位为j时有多少种可能。

①初始化dp[1][j]=1（j = 1 to maxnum）,1位时最高位最高位为j的可能数为1。

②由题意中任何一位数小于右边相邻的数。可以得出状态转移方程

    dp[i][j] = dp[i][j]+dp[i-1][k]（j<k<maxnum）

   将i=2 to m进行更行。

   其中r有j位时总的可能数为sum(dp[i])

注意：当有m位时要进行特殊处理，因为有m位时最高位并不一定能取到maxnum。令x=w%k，最高位只能取到2**x-1

③最后我们将r有i位（2<=i<=m）时的可能数求和即可。

注意事项:

参考代码:

def f(k,w):  
    m = 0               #记录最多能划分的位数
    if w % k == 0:  
        m = w//k  
    else:  
        m = w//k + 1  
  
    maxnum = 2**k      #记录每一位的最大值
    dp = [[0 for j in range(maxnum)] for i in range(m+1)]  
  
    for i in range(1,maxnum):    #初始化dp[1][i]=1
        dp[1][i] = 1  
      
    for i in range(2,m+1):       #将i= 2 to m 时的情况进行更新
        for j in range(1,maxnum-i+1):  
            for k in range(j+1,maxnum-i+2):  
                dp[i][j] = dp[i][j] + dp[i-1][k]  
    ans = 0  
    x = w % k  
    for i in range(2,m):  
        ans = ans + sum(dp[i])  
    for i in range(1,2**x):  
        ans = ans + dp[m][i]  
    print(ans)  
          
  
if __name__ == '__main__':  
    k,w = map(int,input().strip().split())  
    f(k,w)