问题描述:
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17
2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.
Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.
Sample Input
2
10
30
0
Sample Output
1
4
27
问题分析:
二维数组w,其中w[i][j]表示:使用<=i并且>=1的整数序列{1...i}的变系数平方和等于j的多项式个数。
构造递推式:w[i][j] = sum { w[i-1][j-k*i*i] },其中k=0,1,... j-k*i*i >= 0,这个式子的意思是,使用<=i-1并且>=1的整数序列{1...i-1}的变系数平方和等于j-k*i*i的多项式个数的和,这个和等同于,使用<=i并且>=1的整数序列{1...i}的变系数平方和等于j的多项式个数。因为整数序列{1...i-1}的变系数平方和多项式再加上k*i*i就是整数序列{1...i}的变系数平方和多项式。
package com.iteye.caoruntao.zoj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author caoruntao
*
*/
public class SquareCoins {
private static int w[][] = new int[18][301];
public static void compute(){
for(int i=1; i<18; i++){
for(int j=0; j<301; j++){
if(i==1 || j==0){
w[i][j] = 1;
}
else{
w[i][j] = 0;
}
}
}
for(int i=2; i<18; i++){
for(int j=1; j<301; j++){
for(int k=0; j-k*i*i>=0; k++){
w[i][j] += w[i-1][j-k*i*i];
}
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
int n;
compute();
try {
while(!(str = br.readLine()).equalsIgnoreCase("0")){
n = Integer.parseInt(str);
System.out.println(w[17][n]);
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
分享到:
相关推荐
动态规划题解coins.cpp
leetcode 凑硬币 LeetCode_No.322_-零钱兑换 题目介绍 给定不同面额的硬币 coins 和一个总金额 ...动态规划 时间复杂度O(S*n),S为coins的种类数量 空间复杂度O(n) 执行用时:112 ms, 在所有 C++ 提交中击败
Description 设有 n 种不同面值的硬币,各硬币的面值存于数组 T... 对任意钱数0,对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
资源分类:Python库 所属语言:Python 资源全名:Coins-0.1.11.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
coins-security-1.0jar包
动态规划算法学习心得(leetcode) 动态规划算法的实质是更好的优化穷举算法,即把算过的子树记录下来减少计算次数。 储存计算过的子树的数列就是dp数列 使用动态规划有三个条件 1.最值问题 一般动态规划的使用场景是...
2019 Standard Catalog of World Coins, 2001-Date, 13th edition
I = imread( C:\MATLAB701\toolbox\images\imdemos\coins.png ) imshow(I) figure, imhist(I,64)
给定不同面额的硬币 coins 和一个总金额 ...动态规划,转移方程: 用dp[i] 来表示组成i块钱需要最少的硬币数,每个面值的硬币可以拿任意个,因此对于每一个 dp[i] 我们都遍历一遍所有面值,看要不要再拿一个这个面值的
由婴儿创建#1337 步骤1:配置婴儿币\ INITIALIZATION \ config.js 步骤2:使用所需的名称创建一个数据库,然后在其中运行以下sql代码:baby-coins \ babycoins.sql 步骤3:打开cmd,执行命令“ npm install” 第4步...
COINS 编译器基础架构为 Intel x86、Sparc、Arm、Mips、PowerPC 等提供模块化的编译器组件,例如 C 前端、Fortran 前端、优化器、并行器和后端,以便编译器开发人员可以轻松构建自己的通过组合或修改组件或添加新...
硬币-街道网络的连续性 该存储库包含COINS工具的源代码,该工具可以推论街道网络的自然连续性。 对于街道的连续性,计算相邻路段之间的偏转角,用户可以提供所需... 环境与规划B:城市分析与城市科学。 必填项目: @
poj 3260 The Fewest Coins.md
leetcode 和 oj 简介 :balloon: 题目为九章算法DP专题中讲到的题目。 :balloon: 每道题目有好几个程序,这是因为...sort(coins.begin(),coins.end()); //不得不忍受一个排序的时间复杂度 if(amount == 0) { return 0; }
coins.aca056c6.css
动态规划,要求:现有硬币n枚。其价值为v(1,q,q^2……q^n),且每枚硬币重量为一,求价值为Y且重量最小的硬币集合 时间复杂度为O(n*v)
可以使用的各种面值的硬币个数存于数组Coins[1:n]中。 对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
Coins
该文件夹中是三种二值化算法的matlab代码,下面以otsu二值化算法实现为例进行说明: 在Matlab上运行时,可以把该文件夹...I = imread( D:\coins.bmp ) 二值化 I_bw = otsu(I) 查看二值化结果 figure, imshow(I_bw)
# 动态规划思想 dp方程式如下 # dp[0] = 0 # dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length # 回溯法,输出可找的硬币方案 # path[i] 表示经过本次兑换后所剩下的面值,...