欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

手撕代码之“动态规划”

程序员文章站 2024-01-19 20:34:34
文章目录动态规划问题套路剪绳子问题动态规划问题套路(1)确定状态(问题描述中的自变量)和选择(可能改变状态的操作)(2)定义dp表(3)根据选择,思考状态转移的逻辑关系剪绳子问题问题描述 有根长度为m的绳子,把绳子剪成整数长的n段,n<=m,求出每段长度的最大乘积。解题思路使用动态规划的方法求解,按照动态规划的套路开始:状态: 绳子的长度;定义dp: dp[i]表示长度为i的绳子的分段后的最大乘积;选择: 剪和不剪; 不剪切的则为dp[i],自底而上推导:j*dp[i-j]表示剪...

动态规划问题套路

(1)确定状态(问题描述中的自变量)和选择(可能改变状态的操作)
(2)定义dp表
(3)根据选择,思考状态转移的逻辑关系

剪绳子问题

问题描述 有根长度为m的绳子,把绳子剪成整数长的n段,n<=m,求出每段长度的最大乘积。
解题思路
使用动态规划的方法求解,按照动态规划的套路开始:
状态: 绳子的长度;
定义dp: dp[i]表示长度为i的绳子的分段后的最大乘积;
选择: 剪和不剪; 不剪切的则为dp[i],自底而上推导:j*dp[i-j]表示剪切后,第一段长度为j,则剩余长度的最大乘积为dp[i-j],即剪切时候根据第一段长度的而有很多种情况,我们需要一一列举出来;
base_case: 显然,当i<=4时,dp[i]=i;

import java.util.*;
public class Solution {
    public int cutRope(int target) {
        //特判,1=1*1
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        int[] dp=new int[target+1];
        
        //base_case
        for(int i=1;i<=4;i++){
            dp[i]=i;
        }
        //dp[5]=max(dp[5],j*dp[i-j])--->dp[6]---->dp[target]
        for(int i=5;i<=target;i++){
            //j表示剪切后,第一段绳子的长度
            for(int j=1;j<i;j++){
                //有两种选择:
                //不剪dp[i]
                //剪---怎么剪切,按第一段长度依次列举出来,j*dp[i-j]
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            }
        }
        return dp[target];
    }
}

本文地址:https://blog.csdn.net/qq_31032005/article/details/107604852

相关标签: Java Algorithm