小偷与守望者.math库.动态规划.贪心.C-创新互联

1.分别讨论0或1;边界

2.写出递推方程;最优子结构、状态转移方程、重叠子问题

int rob(int* arr, int size){

  int dp[size];int result;

  if(size==0)return 0;

  if(size==1)return arr[0];

  else{

  dp[0]=arr[0];

  dp[1]=arr[1] >arr[0] ? arr[1]:arr[0];

  for (int i = 2; i< size; ++i) {

  dp[i]= dp[i-1]>arr[i]+dp[i-2] ? dp[i-1]:arr[i]+dp[i-2]; //注意arr 和 dp ；dp进入下一次递推

  }

  result=dp[size-1];

  return  result;

低空间写法:

滚轮数组

int rob(int* nums, int numsSize) {
    int retVal = 0;

    if (numsSize == 0) {
        return retV

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧