首页 > 代码库 > nyoj VF函数
nyoj VF函数
大意就是: 在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]); } } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。