蓝桥杯K好数（动态规划）

古城微笑少年丶 2022-06-01 10:47 120阅读 0赞

1、背景：动态规划是在20世纪50年代由美国数学家贝尔曼为研究最优控制问题而提出的，英文叫dynamic  programming。在计                  算机科学界，动态规划法成为一种通用的算法设计技术来求解多阶段决策最优化问题。

2、多阶段决策过程：在实际应用中，经常有这样的一类问题：该问题有n个输入，问题的解由这n个输入的一个子集组成，这个子集必须满足事先给定的条件，这些条件称为约束条件，满足约束条件的解称为可行解。满足约束条件的可行解不只一个，为了衡量这些可行解得优劣，通常以函数的形式给出一定的标准，这些标准函数称为目标函数，使目标函数取得极值的可行解称为最优解，这类问题称为最优化问题。列如:0/1背包问题。

3、多阶段决策过程满足最优性原理：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策的所产生的当前状态，构成一个最优决策序列。换言之，在多阶段决策中，各子问题的解只是与它前面的问题的子问题的解相关，而且各个子问题的解都是相对于当前状态的最优解整个问题的最优解是有各个支问题的最优解构成的。

4、动态规划法设计思想：

动态规划法的思想是将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题的递推关系中，将子问题的解求解一次并填入表中，当需要再次求解子问题时，可以通过查表获得该问题子问题的解，从而避免了大量的重复计算。具体的动态规划法多种多样，但都具有相同的填表形式。

5、动态规划法的一般求解形式：三个阶段

（1）划分子问题:将原问题分解成为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠关系。

（2）确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式（即动态规划函数），这是动态规划法的关键。

（3）填写表格：设计表格，以自底向上的方式计算各个子问题的解并填表，实现动态规划过程。

接下来就是展现正真技术的时候了

正文：

首先大家一起来分析一下这道题

问题描述

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式

输入包含两个正整数，K和L。

输出格式

输出一个整数，表示答案对1000000007取模后的值。

样例输入

4 2

样例输出

咳咳，刚开始我是连题目都看不懂的，语文水平太差。

到底是什么意识呢？

举个例子：4进制的两位数有以下这些：00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 33

相邻两位不相邻的数，就是这些了11、13、20、22、30、31、33

好了，题意懂了，那么就按照步骤去进行吧，

第一步，划分子问题，如果是一位数则都是K好数，如果是两位数只需判断与上一个数是否相邻，相邻的话就加一。

第二步，动态规划函数，就是这样的

if(k!=j-1 && k!=j+1)
                           {
                                f[i][j]+=f[i-1][k];
                                f[i][j]%=1000000007;
                            }

k就是与它相邻的数，循环判断。K就是它的进制，判断从0到K的数是否相邻。

第三步，填表就是

f[i][j]+=f[i-1][k];

把数据保存进去。  
  
所以代码实现就是这样的：

import java.io.*;
    public class Main {
    
       public static void main(String[] args) throws IOException {
            BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
            String s[] = bfr.readLine().split(" +");
           int K = Integer.valueOf(s[0]);
            int L = Integer.valueOf(s[1]);
            int f[][] = new int[L][K];
            int i,j,k,sum=0;
            
           for(j=0;j<K;j++) f[0][j] = 1;
            f[0][0]=0;
            if(L>1)
           {
                  for(i=1;i<L;i++)
                     {
                   for(j=0;j<K;j++)
                   {
                       for(k=0;k<K;k++)
                           if(k!=j-1 && k!=j+1)
                           {
                                f[i][j]+=f[i-1][k];
                                f[i][j]%=1000000007;
                            }
                   }
                     }
           }
            for(j=0;j<K;j++) { sum+=f[L-1][j]; sum%=1000000007; }
            System.out.println(sum);
        }
    }