首页 > 代码库 > nyoj VF函数

nyoj VF函数

2024-07-02 15:09:27   225人阅读

大意就是： 在1到在10的9次方中，找到各个位数和为固定值s的数的个数，

首先我们确定最高位的个数,为1到9；

以后的各位为0，到9；

运用递归的思想，n位数有n-1位数生成

f(n)(s) +=f(n-1)(s-k)(k=0~9)

可以学习背包问题，直接降到一维表示，注意规划方向，从高到底。

package vf;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=82;
        int dp[]=new int[n];

        dp[0]=0;
        int total[]=new int[n];

        for(int m=1;m<=9;m++)
        {
            dp[m]=1;
            total[m]=1;

        }
        

         for(int i1=1;i1<9;i1++)//每次加一位
         {
               
            for(int j=n-1;j>=1;j--)
            {
                int ans=0;
                for(int k=0;k<=9&&k<j;k++)
                {
                    
                    ans+=dp[j-k];
                     
                }
                dp[j]=ans;
                
                total[j]+=dp[j];
                  
            }
            



         }


         Scanner scn=new Scanner(System.in);

  while(scn.hasNext())
  {

                     
            int a=scn.nextInt();
            if(a==1)
            {
            System.out.println(total[a]+1);
            }
            else
            {
                
                System.out.println(total[a]);
                
            }



  }

        
        
        
        
        
        
        
        
        
        
        
        

    }

}


联系
我们