首页 > 其他 > 详细

动态规划问题

时间:2019-03-10 13:28:48      阅读:128      评论:0      收藏:0      [点我收藏+]

HDU-1284

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1284

这是一道背包类型的动态规划题目,题目意思是N块钱,可以有1,2,3元组成,问你有几种兑换方法,简单思考一下,假如说有n元钱,求f(n),f(n)= f(n-1)+f(n-2)+f(n-3)

然后接下来递推或者递归都ok

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int dp[][] = new int[4][32768];
        for (int i = 1; i < 4; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < 32768; j++) {
            dp[1][j] = 1;
        }
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 32768; j++) {
                if (i > j) {
                    dp[i][j] = dp[i - 1][j];
                } else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - i];
            }
        }
        while (in.hasNext()) {
            int n = in.nextInt();
            System.out.println(dp[3][n]);
        }
    }
}

 

 

 

 

动态规划问题

原文:https://www.cnblogs.com/shineyoung/p/10504948.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!