剑指 Offer 14- I. 剪绳子

我服了。动态规划杀我。

可以说一说解决动态规划的思路（只做了两三道就总结了emmm）

1.识别动态规划问题

--重叠子问题：大问题可以分为一个个子问题。和分治策略分割的子问题不同（分治问题的子问题是相互独立的），动态规划的子问题是相互重叠的。对于剪绳子这道题，绳子长度从2到n都分别是一个子问题，重叠性显然看出来。如果用递归策略，自顶向下求解，很多子问题会被重复计算，如求长度是10的绳子，一定会求长度为8（7，6都会求）时的最优解。（这个可能难理解，但是现在不是重点，讲清楚可能要借鉴别人的博客，关于递归问题和动态规划的异同）

--最优子结构：每个子问题都有最优解。且总问题的每个子问题一定是最优的（这句话和本题的联系需要再揣摩）。

--无后效性：子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

2.写出状态，列出状态方程。

这一步是非常重要的，是动态规划思路的核心。也可以说这是一个递推方程。

3.确定边界条件（初始条件）

有了递推方程和初始条件，可以得到所有最优解。

列出状态转移方程的技巧是，首先考虑子问题，思考如何解决该子问题的最后一步，就可以列出来。

长度为i的绳子，设dp[i]是将绳子剪成m段（m是多少不用关心）的最大长度（这个dp数组，即状态，往往是题目要求的问题），这个绳子最后一步是剪出一段长度为j的短绳（j应该从2开始），剩下i-j的绳子是剪还是不剪？

如果剪，dp[i]=dp[i-j]*j

如果不剪,dp[i]=j*(i-j)

长度为i的绳子，剪出j后的dp[i]=max(j*(i-j),dp[i-j]*j)。

每个j都有一个dp[i]，对于每个i应有dp[i]=max(dp[i],max(j*(i-j),dp[i-j]*j))---意思是对每个dp[i]，取最大值存进来。

这一点和0-1背包问题很像，但状态方程有点区别，关键在于0-1背包问题的最后一步是简单的放与不放，这个剪绳子的最后一步是j从2到i-1（不能剪出和i相等或者比i长的长度吧）的每个数都有可能，所以每个j的dp[i]也要比较。

只要状态转移方程写对了，还有初始条件dp[2]=1，就能解决问题，好神奇，根本不关心m段究竟是多少段，如同0-1背包问题里不关心里面的物体分别是什么且有几件一样。神奇。

1 class Solution { 2     public int cuttingRope(int n) { 3      int[] dp =new int[n 1];//在方法里会默认初始化吗？--看来是会的，这样提交没报错 4       5      dp[2]=1; 6      for(int i=3;i<n 1;i  ){ 7          for(int j=2;j<i;j  ){ 8              dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j))); 9          }10      }11      return dp[n];12     }13     14 }