学习动态规划
/*
假设有三种硬币足够多 2,5,7，要求支付某一面额 花费最少的硬币
*/
public class NineChapter_01 {
public static void main(String[] args) {
System.out.println(findMinNum(39));
System.out.println(findMinNumByDp(39));
}
//递归方法
private static int findMinNum(int x) {
if (x==0){ return 0; }
int res = 10000000; //边界条件与限制
if (x>=2){res= Math.min(findMinNum(x-2)+1,res);}
if (x>=5){res= Math.min(findMinNum(x-5)+1,res);}//最后一步 是是什么
if (x>=7){res= Math.min(findMinNum(x-7)+1,res);}
return res;
}
/*
1.确定状态 ，解动态规划是需要看一个数组，数组的每个元素f[i]或者 f[i][j]代表什么
a.最后一步：最优策略中的最后一个决策
b.子问题
2.转移方程：设状态f[x]=最少用多少枚硬币拼出x，对于任意的X f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1};
3.初始条件和边界情况 用转移方程计算不出来 需要自己定义，防止数组越界，还要给一个初始值
4.计算顺序 以一个怎么样的顺序进行计算
*/
//动态规划,设状态f[x]=最少用多少枚硬币拼出x，对于任意的X
// f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1};
private static int findMinNumByDp(int x) {
if (x==0){return 0;}
int[] dp = new int[x+1];
dp[0]=0;
for (int i = 1; i <=x ; i++) {
dp[i]=100000; //先将所有的赋值为最大值
}
for (int i = 0; i <=x ; i++) {
if (i>=2){dp[i]=Math.min(dp[i-2]+1,dp[i]);}
if (i>=5){dp[i]=Math.min(dp[i-5]+1,dp[i]);}
if (i>=7){dp[i]=Math.min(dp[i-7]+1,dp[i]);}
}
return dp[x];
}
//官方代码
private static int findMinNumByDp(int[] A,int M) { //A是含有2,5,7,的数组 ，M是目标
int[] dp=new int[M+1];
int n=A.length;
dp[0]=0;
int i,j;
for ( i = 1; i <=M ; i++) {
dp[i]=Integer.MAX_VALUE;
for ( j = 0; j <n ; j++) {
if (i>=A[j]&&dp[i-A[j]]!=Integer.MAX_VALUE){//边界条件 无穷大不能加1
dp[i]=Math.min(dp[i-A[j]]+1,dp[i]);
}
}
}
if (dp[M]==Integer.MAX_VALUE){
dp[M]=-1;
}
return dp[M];
}
}
//给定m行n列的网格，有一个机器人从左上角（0,0）出发，每一步可以向下或者向右走一步
// 问有多少种不同的方式走到右下角
//计数形式的动态规划
/*
1.确定状态 右下角坐标为（m-1,n-1），那么前一步机器人一定是在（m-2，n-1）或者是（m-1，n-2）中过渡而来的
那么，如果机器人有x种方式从左上角走到（m-2，n-1）
机器人有y种方式从左上角走到（m-1，n-2）
则机器人有x+y种方式走到（m-1，n-1）
子问题 ：机器人现在有多少种方式从左上角走到（m-2，n-1） 和（m-1，n-2）
顺序的定义和转移方程有关
*/
public class Test02 {
public static void main(String[] args) {
int[][] arr = new int[8][9];
System.out.println(walkByDp(arr));
System.out.println(uniquePaths(8,9));
}
//我的代码 代码中有错误定义错了边界
private static int walkByDp(int[][] arr) {
if (arr==null){
return 0;
}
int[][] dp =new int[arr.length+1][arr[0].length+1]; //这里不是+1 注意边界
dp[arr.length][arr[0].length]=1;
int m=arr.length;
int n=arr[0].length;
for (int i = 0; i <=m ; i++) {
dp[i][0]=1;
}
for (int i = 0; i <n ; i++) {
dp[0][i]=1;
}
dp[0][0]=0;
for (int i = 0; i <=m ; i++) {
for (int j = 0; j <=n ; j++) {
if (i>=1&&j>=1)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[arr.length-1][arr[0].length-1];
}
//老师的代码
public static int uniquePaths(int m,int n){
int[][] dp = new int[m][n];
for (int i = 0; i <m ; i++) {
for (int j = 0; j <n ; j++) {
if (i==0||j==0){dp[i][j]=1;}
else {
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
//存在性问题
public boolean canJump(int[] arr){
int n=arr.length;
boolean dp[] =new boolean[n];
dp[0]=true;//第一个点青蛙能跳到
for (int i = 1; i <n ; i++) {
dp[i]=false;
for (int j = 0; j <j ; j++) {
if (dp[j]&&j+arr[j]>=i){//该石头已经确认跳到，而且j+arr[j]能跳的值大于 i dp[i]=true
dp[i]=true;
break;
}
}
}
return dp[n-1];
}
乘积最大子序列
找出一个序列中乘积最大的连续子序列（至少包含一个数）。
样例
样例 1:
输入:[2,3,-2,4]
输出:6
样例 2:
输入:[-1,2,4,1]
输出:8 //非动态规划版本
// dp[i][j]=arr[i]*...arr[j]
//dp[i][j]表示从i到j最大的连续数
public static int maxProduct(int[] nums) {//0---n-1 1....n
// write your code here
int n=nums.length;
int[][] dp= new int[n][n];
for (int i = 0; i <n ; i++) {
for (int j = i; j <n ; j++) {
dp[i][j]=1;
for (int k = i; k <=j ; k++) {
dp[i][j]*=nums[k];
}
}
}
int max=Integer.MIN_VALUE;
for (int i = 0; i <n ; i++) {
for (int j = i; j <n ; j++) {
if (dp[i][j]>=max){
max=dp[i][j];
}
}
}
return max;
}
public int maxProduct2(int[] nums) {
int n = nums.length;
int max = nums[0];
int ans;
for(int i = 0;i < n;++i){
ans = nums[i];
if(ans > max)
max = ans;
if(i != n - 1){
for(int j = i + 1;j < n;++j){
ans *= nums[j];
if(ans > max)
max = ans;
}
}
}
return max;
}
//非动态规划版本
// dp[i][j]=arr[i]*...arr[j]
//dp[i][j]表示从i到j最大的连续数
public static int maxProductByDp(int[] nums) {//0---n-1 1....n
if (nums==null||nums.length<1){
return 0;
}
// write your code here
int n=nums.length;
int max=nums[0];
int min=nums[0];
int result =nums[0];
//每有一个新的数字加入，最大值要么是当前最大值*新数，要么是当前最小值（负数）*新数（负数），要么是当前值。
for (int i = 1; i <n ; i++) {
int temp=max;
max=Math.max(Math.max(max*nums[i],min*nums[i]),nums[i]);
min=Math.min(Math.min(temp*nums[i],min*nums[i]),nums[i]);
if (max>result){
result = max;
}
}
return result;
}
/*
1.确定状态 ，解动态规划是需要看一个数组，数组的每个元素f[i]或者 f[i][j]代表什么
a.最后一步：最优策略中的最后一个决策
b.子问题
2.转移方程：设状态f[x]=最少用多少枚硬币拼出x，对于任意的X f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1};
3.初始条件和边界情况 用转移方程计算不出来 需要自己定义，防止数组越界，还要给一个初始值
4.计算顺序 以一个怎么样的顺序进行计算
*/