动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。适用动态规划的问题必须满足：
/**
* DP Step：
* 1)确定状态：
* i）简单说，即开辟一个数组，数组中元素代表什么？
* ii）两个意识：最后一步和子问题
* 2)转移方程：
* 3)初始条件和边界情况：
* i)初始条件：转移方程无法计算，但是实际又需要的
* 4)计算顺序：
* 一般是从左往右，从上往下。
*
*/
/**
* Analyze: 涉及到（1）计数，e.g.,有多少种方式/方法
* （2）求最大最小问题，e.g.,最长上升子序列、最大数字和
* （3）求存在性：e.g.,是否、能不能
* 一般用动态规划解决。
*/
package DynamicProgramming;
/**
* Question: 需要付27元钱的账单，你有2,5,7,三种零钱若干（假使无穷多）。
* 问：如何用数目最少的零钱组合就可以支付账单？
* Analyze: 涉及到 求最大最小问题，基本操作是 min/max
* DP Step：
* 设F(27)表示拼出27的最优组合数目，F(X)表示拼出X的最少硬币数。
* 1)最后一步：
* 假设需要K枚硬币，最后一枚是ak，则，前K-1枚拼出了(27-ak).
* 我们知道这（K-1）枚拼出（27-ak）是最优的。
* 但是，我们不知道K是多少，ak是多少？
* 2）子问题：
* 子问题：如何用最少硬币拼出（27-ak）？
* 原问题：如何用最少硬币拼出27？
* 将原问题转化成了规模更小的子问题。
* Wait！！！
* K是多少？ak是多少？
* 虽然我们不知道ak是多少，但是，我们知道ak的取值范围：2 5 7
* 所以！
* F(27) = min{F(27-2)+1,F(27-5)+1,F(27-7)+1}
* 3）状态转移方程：
* F[x] = min{F[x-2]+1,F[x-5]+1,F[x-7]+1}
* 4）边界情况：
* x-2、x-5、x-7小于0怎么办？置为无穷大
* 5)初始值：
* F[负数] = INF,F[0] = 0 1->INF:皆可计算
* 6）什么时候停下来？
* 找到27元的最优组合数
* 7）计算顺序？
* 因为F[x]依赖于F[x-2],F[x-5],F[x-7]，所以，从左往右计算。
*
*/
public class Coin {
public static final int INF = 1000000007;
public static void main(String[] args){
int total = 27;
// int count = Rec(total); // 递归版
int count = DP(total); // DP版
System.out.println(count);
}
public static int DP(int money){
// 开辟数组大小 +1
// 含义：dp[i] 表示凑够零钱i所需的最少组合数。
int[] dp = new int[money+1];
// 初始化
dp[0] = 0;
// 状态转移
for (int i=1;i<=money;i++){
dp[i] = min(dp,i-2,i-5,i-7); // 状态转移方程
}
return dp[money];
}
public static int min(int[] a, int i,int j,int k){
int res1 = i<0?INF:(a[i]+1);
int res2 = j<0?INF:(a[j]+1);
int res3 = k<0?INF:(a[k]+1);
return (res1<res2?res1:res2)<res3?(res1<res2?res1:res2):res3;
}
public static int Rec(int money){
/**
* 递归的过程，可以用递归树来模拟：从上往下，从左往右。
*/
if (money==0)
return 0;
if (money==1)
return INF; // 此处为什么不用Integer.MAX_VALUE？因为溢出问题！变成负数。
int res = Integer.MAX_VALUE;
if (money>=2){
res = Math.min(Rec(money-2)+1,res);
}
if (money>=5) {
res = Math.min(Rec(money - 5) + 1, res);
}
if (money>=7) {
res = Math.min(Rec(money - 7) + 1, res);
}
return res;
}
}
package DynamicProgramming;
/***
* Question：有一个二维矩阵，机器人从左上角走到右下角，每次只能向右或者向下走。
* 问，机器人有多少种路径？
* Analyze：计数问题：基本操作是 加法+
* DP Step：
* 1）确定状态：
* dp[i][j] 含义：机器人走到（i，j）的方法；
* 最后一步：
* 因为最后一步到达(m-1,n-1)，机器人的倒数第二步可能位置：上：(m-2,n-1)，左：(m-1,n-2)
* 则：dp[m-1][n-1] = dp[m-2][n-1]+dp[m-1][n-2]
* 子问题：
* 问：机器人走到(m-2,n-1)，(m-1,n-2)有多少种方法？
* 2）状态转移方程：
* dp[i][j] = dp[i-1][j]+dp[i][j-1]
* 3）初始条件和边界情况：
* 初始条件：dp[0][0] = 1
* i-1、j-1出现负数时，为0.
* 另一种初始化方法：
* 直接把边界i=0、j=0的时候初始化为1
* 则 dp[1][0]=dp[0][0]+dp[1][-1]=1+0=1
* 机器人走到(m-1,n-1)结束
* 4）计算顺序：
* 从左往右，从上往下。
*
*/
public class UniquePaths {
public static void main(String[] args) {
int[][] map = new int[2][2];
int count = uniquePaths(map);
System.out.println(count);
}
public static int uniquePaths(int[][] map){
int count = 0;
map[0][0] = 1;
for (int i=0;i<map.length;i++){
for (int j = 0; j < map[i].length; j++) {
if (i==0&&j==0)
continue;
int up = (i-1<0||j<0)?0:map[i-1][j];
int left = (i<0||j-1<0)?0:map[i][j-1];
map[i][j] = up + left;
// System.out.println(i+","+j+" : "+map[i][j]);
}
}
count = map[map.length-1][map[0].length-1];
return count;
}
}
package DynamicProgramming;
/**
* Question：跳跃游戏，有n块石头，分别在x轴上从0到n-1.一只青蛙从石头0想跳到石头n-1.
* 如果，在第i个石头上，它最多可以跳距离为ai。
* 问：青蛙能否跳到石头n-1？
* Analyze: 存在性问题。基本操作：OR/AND
* DP Step：
* 1）确定状态：
* F[i]表示青蛙能否跳到第i个石头上。
* i）最后一步：
* 最后一步在（n-1）位置，那么上一步呢？
* 假设在第i个位置处，那么能确定吗？
* 不能。但是i满足两个条件：
* condition1：青蛙可以跳到石头i；
* condition2：青蛙可以从石头i跳到n-1.
* ii）子问题：
* 青蛙能否跳到石头i？
* 2）状态转移方程：
* F[i] = OR_{0<=j<i}(F[i] AND (F[j]+a[j]>i))
* 3）初始条件和边界情况
* F[0] = true. 可达
* i = n-1时停止
* 4）计算顺序：
* 从左往右。
*/
public class Jump {
public static void main(String[] args) {
int[] ar = new int[]{2,3,1,1,4};
boolean flag = junmp(ar);
System.out.println(flag);
int[] ar1 = new int[]{2,1,1,0,4};
boolean flag1 = junmp(ar1);
System.out.println(flag1);
}
public static boolean junmp(int[] ar){
boolean[] flag = new boolean[ar.length];
flag[0] = true;
for (int i=1;i<ar.length;i++){
for (int j=0;j<i;j++){
if (flag[j] && j+ar[j]>=i){
flag[i] = true;
break;
}
}
}
return flag[ar.length-1];
}
}
问题：
有n个中继器，置于长度为n的线路。（每隔单位距离，放置一个中继器），中继器i能传输的信号距离由数组num[i]决定。
问：
从节点0传到节点n-1，需要的最少中转次数？
测试样例：
输入：
4
2 3 1 1
输出：
2
分析：
F[i]：表示信号传到节点i，所需的最少中转次数。
1）最后一步：信号从节点k传到节点n-1.
问题：节点k，如何确定？？？
显然，节点k要满足一定条件：即信号可以从节点k传到节点n-1。
2）子问题：从节点0传到节点k，需要的最少中转次数？
3）状态转移方程：
F[i] = min{F[k]+1} // k节点 有约束条件。
4）初始化：
F[0] = 1; // 表示从0号节点传出去，算一次中转。
5）边界：信号传到节点n-1结束。
6）计算顺序：从左往右。
package DynamicProgramming;
public class HW03 {
public static void main(String[] args) {
int[] nums = new int[]{3,2,1,1,1};
System.out.println(minNum(nums));
}
public static int minNum(int[] nums){
int[] need = new int[nums.length]; // 表示到达节点i需要的最少中继器数目
// 初始化
need[0] = 1; // 0号节点出发 第一次中转
// 状态转移
for (int i=1;i<nums.length;i++){
need[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
// 判断中继器j是否可以到达节点i
if (nums[j]+j>=i){
// 到达节点i可以经过中继器j
// 比较 是否为最少中转次数
need[i] = Math.min(need[i], need[j]+1);
}
}
}
return need[nums.length-1];
}
}
首先给扑克牌中每张牌设定一个编号，下面算法实现的编号规则如下： u 红桃按照从...
一、MVC MVC模式的意思是，软件可以分成三个部分。 视图（View）：用户界面。 控...
我们知道微软将会在今年给Windows10更换全新设计的UI，让Windows10的界面更加整...
git工作区，暂存区，版本库之间的关系： 我们建立的项目文件夹就是工作区，在初...
前言 关于Window，你了解多少呢?看看下面这些问题你都能答上来吗。 如果你遇到这...
大家好，今天我们来简单的聊一聊缓存问题。什么是缓存呢?它在系统设计中是在一个...
一、简介 本设计为硬币图像识别统计装置通过数码相机获取平铺无重叠堆积的硬币的...
从功能测试、性能测试、界面测试、安全性测试、易用性、兼容性测试、震动测试七...
本文实例讲述了jsp中page指令用法。分享给大家供大家参考。具体如下： 一、JSP ...
今日国内领先的智能数据服务运营商觉非科技完成近亿元A轮融资。本轮融资由和高资...
