Java教程

动态规划 立扣题

本文主要是介绍动态规划 立扣题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

剪绳子

立扣343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

func cuttingRope(n int) int { // n 米长的绳子
	dp := make([]int, n+1) //范围从1到n
	dp[1] = 1
	dp[2] = 1
	for i := 3; i < n+1; i++ {
		curMax := 1
		for j := 1; j <= i; j++ {
			// 要么直接分成 i 和 i-j 两段，要么将剩下的一段继续分割
			curMax = Max(curMax, Max(j*dp[i-j], j*(i-j)))
		}
		dp[i] = curMax
	}
	return dp[n]
}

func Max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
这篇关于动态规划 立扣题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航