牛客网NC77-20.7.23-dp(动态规划（））
链接：牛客网NC77链接
题意：
文章图片
输入：n,x,a[] (n<=20,x<=100,a[i][0]<=50,a[i][1]<=20)
输出：方法数
分析：想象这些钱是一堆一堆的，相同的钱放在一堆里面，有n堆，然后一个从第一堆开始拿钱，直到拿到的钱的值之和等于目标面值x, 在每一堆钱面前有着多种拿法，可以拿一张，两张…只要目标钱数-已经拿的钱数>=要拿的张数面值，这样在一堆面前有着多种状态，可以用递归实现状态的前进与后退，分析一下，最坏情况堆钱有w种拿法，递归n层，wn次递归，w<=20,n<=20,最坏2020，嗞，得，完蛋了。幸好奥，这种状态得转换还可以通过dp来达到，我还记得以前看的书说了，对于动态规划，一是要明确状态，二是要得到状态转移。我们可以定义状态dp[i][j]是有i种牛币目标币值j的换钱方法，所以初始状态是什么呢，是0种牛币目标币值0的换钱方法为1，即是dp[0][0]=1,当然dp[i][0]当然都是0，当时我也有这样的疑问，看似初始状态有很多，但总有一个或几个是不能被其他状态转移的，这才是初始状态，看一下状态转移方程是怎么样的呢，从dp[i][j]能转移到什么地方呢？dp[i][j]可以转移到
dp[i+1][j+k*a[i+1][0]]，k∈ \in ∈[0,a[i+1][1]]是拿取得第i+1种的钱币数，a[i+1][0]是第i+1种牛币的币值，a[i+1][1]是第i+1种牛币的数量，找找还有其他的转移吗，没了就得到如下状态转移方程：
dp[i+1][j+k*a[i+1][0]+=dp[i][j], k∈ \in ∈[0,a[i+1][1]]j+k*a[i+1]<=x
当然，我想过，如果想想，dp[i]][j]可以由什么地方转移过来呢，看似是这样：
dp[i][j]=dp[i-1][j-k*a[i][0]],k∈ \in ∈[0,a[i+1][1]]j+k*a[i+1]<=x
但是实际上dp[i-1][j-k*a[i][0]]的状态没有得到，所以这样是错误的。
思路：坐下来冷静分析然后dp
代码：
import java.util.*;
public class Solution {
/**
*
* @param n int整型 ：牛币值种类数
* @param x int整型 ：牛妹拥有的钱数
* @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
* @return int整型
*/
public int solve (int n, int x, int[][] a) {
// write code here
int[][] dp = new int[n+1][x+1];
dp[0][0]=1;
for(int i=0;
i【牛客网NC77-20.7.23-dp(动态规划（））】等下你电瓶车就不见…
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 猎杀IP
- 自媒体形势分析
- 数学大作战
- 使用协程爬取网页，计算网页数据大小
- 【亲测好用】高逼格配色网站推荐
- 2018.03.18
- 星期天的下午茶（一）
- 很多网红在用的素颜霜，你知道它是属于护肤品还是化妆品吗（）
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会